Count minimum factor jumps required to reach the end of an Array | C ++ 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 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 ; Driver code ; Pre - calculating the factors ; Function call
#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 n ) { for ( int i = 0 ; i <= 100005 ; i ++ ) { dp [ i ] = INT_MAX ; } dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( auto j : factors [ arr [ i ] ] ) { if ( i + j < n ) dp [ i + j ] = min ( dp [ i + j ] , 1 + dp [ i ] ) ; } } return dp [ n - 1 ] ; } int main ( ) { precompute ( ) ; int arr [ ] = { 2 , 8 , 16 , 55 , 99 , 100 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << solve ( arr , n ) ; }