Minimum count of digits required to obtain given Sum
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)