Given a number N, the task is to find the minimum number of operations required to reduce the number N to zero by subtracting the given number by any digit present in it.
Examples:
Input: N = 4
Output: 1
Explanation:
Here 4 is the only digit present hence 4 – 4 = 0 and only one operation is required.Input: N = 17
Output: 3
Explanation:
The given integer is 17 and the steps of reduction are:
17 -> 17 – 7 = 10
10 -> 10 – 1 = 9
9 -> 9 – 9 = 0.
Hence 3 operations are required.
Approach: This problem can be solved using Dynamic Programming.
For any given number N, traverse each digit in N and recursively check by subtracting each digit one by one until N reduces to 0. But performing recursion will make the time complexity of the approach exponential.
Therefore, the idea is use an array(say dp[]) of size (N + 1) such that dp[i] will store the minimum number of operations needed to reduce i to 0.
For every digit x in the number N, the recurrence relation used is given by:
dp[i] = min(dp[i], dp[i-x] + 1),
where dp[i] will store the minimum number of operations needed to reduce i to 0.
We will use Bottom-Up Approach to fill the array dp[] from 0 to N and then dp[N] will give the minimum number of operations for N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N int reduceZero( int N) { // Initialise dp[] to steps vector< int > dp(N + 1, 1e9); dp[0] = 0; // Iterate for all elements for ( int i = 0; i <= N; i++) { // For each digit in number i for ( char c : to_string(i)) { // Either select the number // or do not select it dp[i] = min(dp[i], dp[i - (c - '0' )] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code int main() { // Given Number int N = 25; // Function Call cout << reduceZero(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N static int reduceZero( int N) { // Initialise dp[] to steps int []dp = new int [N + 1 ]; for ( int i = 0 ; i <= N; i++) dp[i] = ( int ) 1e9; dp[ 0 ] = 0 ; // Iterate for all elements for ( int i = 0 ; i <= N; i++) { // For each digit in number i for ( char c : String.valueOf(i).toCharArray()) { // Either select the number // or do not select it dp[i] = Math.min(dp[i], dp[i - (c - '0' )] + 1 ); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code public static void main(String[] args) { // Given Number int N = 25 ; // Function Call System.out.print(reduceZero(N)); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approach # Function to reduce an integer N # to Zero in minimum operations by # removing digits from N def reduceZero(N): # Initialise dp[] to steps dp = [ 1e9 for i in range (N + 1 )] dp[ 0 ] = 0 # Iterate for all elements for i in range (N + 1 ): # For each digit in number i for c in str (i): # Either select the number # or do not select it dp[i] = min (dp[i], dp[i - ( ord (c) - 48 )] + 1 ) # dp[N] will give minimum # step for N return dp[N] # Driver Code N = 25 # Function Call print (reduceZero(N)) # This code is contributed by Sanjit_Prasad |
C#
// C# program for the above approach using System; class GFG{ // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N static int reduceZero( int N) { // Initialise []dp to steps int []dp = new int [N + 1]; for ( int i = 0; i <= N; i++) dp[i] = ( int ) 1e9; dp[0] = 0; // Iterate for all elements for ( int i = 0; i <= N; i++) { // For each digit in number i foreach ( char c in String.Join( "" , i).ToCharArray()) { // Either select the number // or do not select it dp[i] = Math.Min(dp[i], dp[i - (c - '0' )] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code public static void Main(String[] args) { // Given Number int N = 25; // Function Call Console.Write(reduceZero(N)); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program for the above approach // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N function reduceZero(N) { // Initialise dp[] to steps var dp = Array(N + 1).fill(1000000000); dp[0] = 0; // Iterate for all elements for ( var i = 0; i <= N; i++) { // For each digit in number i for ( var j =0; j< i.toString().length; j++) { // Either select the number // or do not select it dp[i] = Math.min(dp[i], dp[i - (i.toString()[j] - '0' )] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code // Given Number var N = 25; // Function Call document.write( reduceZero(N)); </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!