Count minimum factor jumps required to reach the end of an Array | 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 INT_MAX ; 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 ; Pre - calculating the factors ; Function call
var factors = Array . from ( Array ( 100005 ) , ( ) => Array ( ) ) ; var dp = Array ( 100005 ) ; function precompute ( ) { for ( var i = 1 ; i <= 100000 ; i ++ ) { for ( var j = i ; j <= 100000 ; j += i ) factors [ j ] . push ( i ) ; } } function solve ( arr , n ) { for ( var i = 0 ; i <= 100005 ; i ++ ) { dp [ i ] = 1000000000 ; } dp [ 0 ] = 0 ; for ( var i = 0 ; i < n ; i ++ ) { for ( var j of factors [ arr [ i ] ] ) { if ( i + j < n ) dp [ i + j ] = Math . min ( dp [ i + j ] , 1 + dp [ i ] ) ; } } return dp [ n - 1 ] ; } precompute ( ) ; var arr = [ 2 , 8 , 16 , 55 , 99 , 100 ] ; var n = arr . length document . write ( solve ( arr , n ) ) ;