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 Nint 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 Codeint main(){ // Given Number int N = 25; // Function Call cout << reduceZero(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to reduce an integer N// to Zero in minimum operations by// removing digits from Nstatic 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 Codepublic 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 Ndef 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 CodeN = 25# Function Callprint(reduceZero(N))# This code is contributed by Sanjit_Prasad |
C#
// C# program for the above approachusing System;class GFG{// Function to reduce an integer N// to Zero in minimum operations by// removing digits from Nstatic 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 Codepublic 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 Nfunction 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 Numbervar N = 25;// Function Calldocument.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!
