Min number of operations to reduce N to 0 by subtracting any digits from N

0 0 4 minutes read

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>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!