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 digitsvoid 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 Codeint main(){ int n1 = 24; int n2 = 14; mindigits(n1); mindigits(n2);} |
Java
// Java program to implement// the above approach// required to make the given sumimport 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 digitsdef 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 Codeif __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 approachusing System;class GFG{// Function to print the minimum// count of digitsstatic 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 Codepublic 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
