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