Count minimum factor jumps required to reach the end of an Array | C ++ 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 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 ; Driver code ; pre - calculating the factors
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > factors [ 100005 ] ; int dp [ 100005 ] ; void precompute ( ) { for ( int i = 1 ; i <= 100000 ; i ++ ) { for ( int j = i ; j <= 100000 ; j += i ) { factors [ j ] . push_back ( i ) ; } } } int solve ( int arr [ ] , int k , int n ) { if ( k == n - 1 ) { return 0 ; } if ( k >= n ) { return INT_MAX ; } if ( dp [ k ] ) { return dp [ k ] ; } int ans = INT_MAX ; for ( auto j : factors [ arr [ k ] ] ) { int res = solve ( arr , k + j , n ) ; if ( res != INT_MAX ) { ans = min ( ans , res + 1 ) ; } } return dp [ k ] = ans ; } int main ( ) { precompute ( ) ; int arr [ ] = { 2 , 8 , 16 , 55 , 99 , 100 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << solve ( arr , 0 , n ) ; }