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 ; Driver code ; pre - calculating the factors
factors = [ [ ] for i in range ( 100005 ) ] ; NEW_LINE dp = [ 0 for i in range ( 100005 ) ] ; NEW_LINE def precompute ( ) : NEW_LINE INDENT for i in range ( 1 , 100001 ) : NEW_LINE INDENT for j in range ( i , 100001 , i ) : NEW_LINE INDENT factors [ j ] . append ( i ) ; NEW_LINE DEDENT DEDENT DEDENT def solve ( arr , k , n ) : NEW_LINE INDENT if ( k == n - 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( k >= n ) : NEW_LINE INDENT return 1000000000 NEW_LINE DEDENT if ( dp [ k ] ) : NEW_LINE INDENT return dp [ k ] ; NEW_LINE DEDENT ans = 1000000000 NEW_LINE for j in factors [ arr [ k ] ] : NEW_LINE INDENT res = solve ( arr , k + j , n ) ; NEW_LINE if ( res != 1000000000 ) : NEW_LINE INDENT ans = min ( ans , res + 1 ) ; NEW_LINE DEDENT DEDENT dp [ k ] = ans ; NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT precompute ( ) NEW_LINE arr = [ 2 , 8 , 16 , 55 , 99 , 100 ] NEW_LINE n = len ( arr ) NEW_LINE print ( solve ( arr , 0 , n ) ) NEW_LINE DEDENT