Minimum count of digits required to obtain given Sum

0 0 3 minutes read

Given an integer N, the task is to find the minimum number of digits required to generate a number having the sum of digits equal to N.

Examples:

Input: N = 18
Output: 2
Explanation:
The number with smallest number of digits having sum of digits equal to 18 is 99.

Input: N = 28
Output: 4
Explanation:
4-digit numbers like 8884, 6877, etc are the smallest in length having sum of digits equal to 28.

Approach: The problem can be solved by the following observations:

Increment count by 9. Therefore, now count is equal to the number of 9’s in the shortest number. Reduce N to N % 9
Now, if N exceeds 0, increment count by 1.
Finally, print count as the answer.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// minimum count of digits
void mindigits(int n)
{
    // IF N is divisible by 9
    if (n % 9 == 0) {
 
        // Count of 9's is the answer
        cout << n / 9 << endl;
    }
    else {
 
        // If remainder is non-zero
        cout << (n / 9) + 1 << endl;
    }
}
 
// Driver Code
int main()
{
    int n1 = 24;
    int n2 = 14;
    mindigits(n1);
    mindigits(n2);
}

Java

// Java program to implement
// the above approach
// required to make the given sum
import java.util.*;
 
class Main {
 
    // Function to print the minimum
    // count of digits
    static void mindigits(int n)
    {
 
        // IF N is divisible by 9
        if (n % 9 == 0) {
 
            // Count of 9's is the answer
            System.out.println(n / 9);
        }
        else {
 
            // If remainder is non-zero
            System.out.println((n / 9) + 1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n1 = 24;
        int n2 = 18;
        mindigits(n1);
        mindigits(n2);
    }
}

Python3

# Python3 program to implement
# the above approach
 
# Function to print the minimum
# count of digits
def mindigits(n):
     
    # IF N is divisible by 9
    if (n % 9 == 0):
 
        # Count of 9's is the answer
        print(n // 9);
    else:
 
        # If remainder is non-zero
        print((n // 9) + 1);
 
# Driver Code
if __name__ == '__main__':
     
    n1 = 24;
    n2 = 18;
     
    mindigits(n1);
    mindigits(n2);
 
# This code is contributed by amal kumar choubey

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to print the minimum
// count of digits
static void mindigits(int n)
{
     
    // IF N is divisible by 9
    if (n % 9 == 0)
    {
         
        // Count of 9's is the answer
        Console.WriteLine(n / 9);
    }
    else
    {
         
        // If remainder is non-zero
        Console.WriteLine((n / 9) + 1);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int n1 = 24;
    int n2 = 18;
     
    mindigits(n1);
    mindigits(n2);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to implement
// the above approach
// required to make the given sum
 
    // Function to print the minimum
    // count of digits
    function mindigits(n)
    {
  
        // IF N is divisible by 9
        if (n % 9 == 0) {
  
            // Count of 9's is the answer
            document.write(Math.floor(n / 9) + "<br/>");
        }
        else {
  
            // If remainder is non-zero
            document.write(Math.floor(n / 9) + 1 + "<br/>");
        }
    }
 
// Driver Code
 
        let n1 = 24;
        let n2 = 18;
        mindigits(n1);
        mindigits(n2);
            
</script>

Output:

3
2

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

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!