Minimum number of operations required to reduce N to 0 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int downToZero ( int n ) { if ( n <= 3 ) return n ; vector < int > dp ( n + 1 , -1 ) ; dp [ 0 ] = 0 ; dp [ 1 ] = 1 ; dp [ 2 ] = 2 ; dp [ 3 ] = 3 ; int sqr ; for ( int i = 4 ; i <= n ; i ++ ) { sqr = sqrt ( i ) ; int best = INT_MAX ; while ( sqr > 1 ) { if ( i % sqr == 0 ) { best = min ( best , 1 + dp [ sqr ] ) ; } sqr -- ; } best = min ( best , 1 + dp [ i - 1 ] ) ; dp [ i ] = best ; } return dp [ n ] ; } int main ( ) { int n = 4 ; cout << downToZero ( n ) ; return 0 ; }