Minimum number of operations required to reduce N to 0 | Python3 program to implement the above approach ; Function to count the minimum steps required to reduce n ; Base case ; Allocate memory for storing intermediate results ; Store base values ; Stores square root of each number ; Compute square root ; Use rule 1 to find optimized answer ; Check if it perfectly divides n ; Use of rule 2 to find the optimized answer ; Store computed value ; Return answer ; Driver Code
import math NEW_LINE import sys NEW_LINE def downToZero ( n ) : NEW_LINE INDENT if ( n <= 3 ) : NEW_LINE INDENT return n NEW_LINE DEDENT dp = [ - 1 ] * ( n + 1 ) NEW_LINE dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = 1 NEW_LINE dp [ 2 ] = 2 NEW_LINE dp [ 3 ] = 3 NEW_LINE for i in range ( 4 , n + 1 ) : NEW_LINE INDENT sqr = ( int ) ( math . sqrt ( i ) ) NEW_LINE best = sys . maxsize NEW_LINE while ( sqr > 1 ) : NEW_LINE INDENT if ( i % sqr == 0 ) : NEW_LINE INDENT best = min ( best , 1 + dp [ sqr ] ) NEW_LINE DEDENT sqr -= 1 NEW_LINE DEDENT best = min ( best , 1 + dp [ i - 1 ] ) NEW_LINE dp [ i ] = best NEW_LINE DEDENT return dp [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE print ( downToZero ( n ) ) NEW_LINE DEDENT