Count minimum factor jumps required to reach the end of an Array | Java code to count minimum factor jumps to reach the end of array ; vector to store factors of each integer ; dp array ; Precomputing all factors of integers from 1 to 100000 ; Function to count the minimum jumps ; If we reach the end of array , no more jumps are required ; If the jump results in out of index , return Integer . MAX_VALUE ; If the answer has been already computed , return it directly ; Else compute the answer using the recurrence relation ; Iterating over all choices of jumps ; Considering current factor as a jump ; Jump leads to the destination ; Return ans and memorize it ; Driver code ; pre - calculating the factors
import java . util . * ; class GFG { static Vector < Integer > [ ] factors = new Vector [ 100005 ] ; static int [ ] dp = new int [ 100005 ] ; static void precompute ( ) { for ( int i = 0 ; i < factors . length ; i ++ ) factors [ i ] = new Vector < Integer > ( ) ; for ( int i = 1 ; i <= 100000 ; i ++ ) { for ( int j = i ; j <= 100000 ; j += i ) { factors [ j ] . add ( i ) ; } } } static int solve ( int arr [ ] , int k , int n ) { if ( k == n - 1 ) { return 0 ; } if ( k >= n ) { return Integer . MAX_VALUE ; } if ( dp [ k ] != 0 ) { return dp [ k ] ; } int ans = Integer . MAX_VALUE ; for ( int j : factors [ arr [ k ] ] ) { int res = solve ( arr , k + j , n ) ; if ( res != Integer . MAX_VALUE ) { ans = Math . min ( ans , res + 1 ) ; } } return dp [ k ] = ans ; } public static void main ( String [ ] args ) { precompute ( ) ; int arr [ ] = { 2 , 8 , 16 , 55 , 99 , 100 } ; int n = arr . length ; System . out . print ( solve ( arr , 0 , n ) ) ; } }