Count minimum factor jumps required to reach the end of an Array | Java program for bottom up approach ; Vector to store factors of each integer ; Initialize the dp array ; Precompute all the factors of every integer ; Function to count the minimum factor jump ; Initialise minimum jumps to reach each cell as Integer . MAX_VALUE ; 0 jumps required to reach the first cell ; Iterate over all cells ; Calculating for each jump ; If a cell is in bound ; Return minimum jumps to reach last cell ; Driver code ; Pre - calculating the factors ; Function call
import java . util . * ; class GFG { @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] factors = new Vector [ 100005 ] ; static int [ ] dp = new int [ 100005 ] ; static void precompute ( ) { 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 n ) { for ( int i = 0 ; i < 100005 ; i ++ ) { dp [ i ] = Integer . MAX_VALUE ; } dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j : factors [ arr [ i ] ] ) { if ( i + j < n ) dp [ i + j ] = Math . min ( dp [ i + j ] , 1 + dp [ i ] ) ; } } return dp [ n - 1 ] ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < factors . length ; i ++ ) factors [ i ] = new Vector < Integer > ( ) ; precompute ( ) ; int arr [ ] = { 2 , 8 , 16 , 55 , 99 , 100 } ; int n = arr . length ; System . out . print ( solve ( arr , n ) ) ; } }