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 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
using System ; using System . Collections . Generic ; class GFG { static List < List < int > > factors = new List < List < int > > ( ) ; static int [ ] dp ; 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 ] = int . MaxValue ; } dp [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { foreach ( int j in factors [ arr [ i ] ] ) { if ( i + j < n ) dp [ i + j ] = Math . Min ( dp [ i + j ] , 1 + dp [ i ] ) ; } } return dp [ n - 1 ] ; } static public void Main ( ) { for ( int i = 0 ; i < 100005 ; i ++ ) factors . Add ( new List < int > ( ) ) ; dp = new int [ 100005 ] ; precompute ( ) ; int [ ] arr = { 2 , 8 , 16 , 55 , 99 , 100 } ; int n = arr . Length ; Console . Write ( solve ( arr , n ) ) ; } }