Count minimum factor jumps required to reach the end of an Array | 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 ; 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
factors = [ [ ] for i in range ( 100005 ) ] ; NEW_LINE dp = [ 1000000000 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 , n ) : NEW_LINE INDENT dp [ 0 ] = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in factors [ arr [ i ] ] : NEW_LINE INDENT if ( i + j < n ) : NEW_LINE INDENT dp [ i + j ] = min ( dp [ i + j ] , 1 + dp [ i ] ) ; NEW_LINE DEDENT DEDENT DEDENT return dp [ n - 1 ] ; 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 , n ) ) NEW_LINE DEDENT