Given two positive integers N and K, the task is to find the smallest number whose sum of digits is N and every distinct digit in that number occurs at most K times. If no such number exists, print “-1”.
Examples:
Input: N = 25, K = 3
Output: 799
Explanation: Sum of digits of the number = (7 + 9 + 9) = 25 and is the smallest possible.Input: N =100, K = 2
Output: -1
Approach: The given problem can be solved using Greedy Approach. Follow the steps to solve the problem:
- The maximum possible sum of digits of any number having each digit occurring at most K times is K * 45.
- Initialize a string, say res, to store the resultant string formed.
- If N is greater than K * 45, no such number can be obtained. Therefore, print “-1”.
- Otherwise, keep subtracting every number starting from 9 to 1, from N, at most K times. Add the current digit to res. Continue until N is smaller than the current digit.
- If N is smaller than the current digit, insert N as a digit to res.
- After completing the above steps, print the string res in the reversed order as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the smallest number // whose sum of digits is N and each // digit occurring at most K times void findSmallestNumberPossible( int N, int K) { // Maximum sum possible using // each digit at most K times if (N > 45 * K) { cout << "-1" ; return ; } // Append smallest number into // the resultant string string res = "" ; int count = 0; // Iterate over the range [9, 1] for ( int i = 9; i >= 1;) { // If the count of the digit // is K, then update count and // check for the next digit if (count == K) { i--; count = 0; } // If N is greater than // current digit if (N > i) { // Subtract i from N N -= i; // Insert i as a digit res += ( char )48 + i; } else { // Insert remaining N // as a digit res += ( char )N + 48; N = 0; break ; } // Increment count count++; } // Reverse the string reverse(res.begin(), res.end()); // Print the answer cout << res; } // Driver Code int main() { int N = 25, K = 3; // Function Call findSmallestNumberPossible(N, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to find the smallest number // whose sum of digits is N and each // digit occurring at most K times static void findSmallestNumberPossible( int N, int K) { // Maximum sum possible using // each digit at most K times if (N > 45 * K) { System.out.print( "-1" ); return ; } // Append smallest number into // the resultant string StringBuilder res = new StringBuilder(); int count = 0 ; // Iterate over the range [9, 1] for ( int i = 9 ; i >= 1 😉 { // If the count of the digit // is K, then update count and // check for the next digit if (count == K) { i--; count = 0 ; } // If N is greater than // current digit if (N > i) { // Subtract i from N N -= i; // Insert i as a digit res.append(( char )( '0' + i)); } else { // Insert remaining N // as a digit res.append(( char )( '0' + N)); N = 0 ; break ; } // Increment count count++; } // Reverse the string res.reverse(); // Print the answer System.out.print(res.toString()); } // Driver Code public static void main(String[] args) { int N = 25 , K = 3 ; // Function Call findSmallestNumberPossible(N, K); } } // This code is contributed by jithin |
Python3
# Python3 program for the above approach # Function to find the smallest number # whose sum of digits is N and each # digit occurring at most K times def findSmallestNumberPossible(N, K) : # Maximum sum possible using # each digit at most K times if (N > 45 * K) : print ( "-1" , endl = ""); return ; # Append smallest number into # the resultant string res = ""; count = 0 ; # Iterate over the range [9, 1] i = 9 ; while i > = 1 : # If the count of the digit # is K, then update count and # check for the next digit if (count = = K) : i - = 1 ; count = 0 ; # If N is greater than # current digit if (N > i) : # Subtract i from N N - = i; # Insert i as a digit res + = chr ( 48 + i); else : # Insert remaining N # as a digit res + = chr (N + 48 ); N = 0 ; break ; # Increment count count + = 1 ; # Reverse the string res = res[:: - 1 ] # Print the answer print (res, end = ""); # Driver Code if __name__ = = "__main__" : N = 25 ; K = 3 ; # Function Call findSmallestNumberPossible(N, K); # This code is contributed by AnkThon |
C#
// C# program to implement // the above approach using System; class GFG { // Function to find the smallest number // whose sum of digits is N and each // digit occurring at most K times static void findSmallestNumberPossible( int N, int K) { // Maximum sum possible using // each digit at most K times if (N > 45 * K) { Console.Write( "-1" ); return ; } // Append smallest number into // the resultant string string res = "" ; int count = 0; // Iterate over the range [9, 1] for ( int i = 9; i >= 1;) { // If the count of the digit // is K, then update count and // check for the next digit if (count == K) { i--; count = 0; } // If N is greater than // current digit if (N > i) { // Subtract i from N N -= i; // Insert i as a digit res += ( char )( '0' + i); } else { // Insert remaining N // as a digit res += ( char )( '0' + N); N = 0; break ; } // Increment count count++; } // Reverse the string string ans = "" ; for ( int i = res.Length - 1; i >= 0; i--) { ans += res[i] + "" ; } // Print the answer Console.WriteLine(ans); } // Driver Code public static void Main() { int N = 25, K = 3; // Function Call findSmallestNumberPossible(N, K); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the smallest number // whose sum of digits is N and each // digit occurring at most K times function findSmallestNumberPossible(N, K) { // Maximum sum possible using // each digit at most K times if (N > 45 * K) { document.write( "-1" ); return ; } // Append smallest number into // the resultant string var res = "" ; var count = 0; // Iterate over the range [9, 1] for ( var i = 9; i >= 1; ) { // If the count of the digit // is K, then update count and // check for the next digit if (count === K) { i--; count = 0; } // If N is greater than // current digit if (N > i) { // Subtract i from N N -= i; // Insert i as a digit res += String.fromCharCode( "0" .charCodeAt(0) + i); } else { // Insert remaining N // as a digit res += String.fromCharCode( "0" .charCodeAt(0) + N); N = 0; break ; } // Increment count count++; } // Reverse the string var ans = "" ; for ( var i = res.length - 1; i >= 0; i--) { ans += res[i] + "" ; } // Print the answer document.write(ans); } // Driver Code var N = 25, K = 3; // Function Call findSmallestNumberPossible(N, K); </script> |
799
Time Complexity: O(log10N)
Auxiliary Space: O(1)
Another Approach:
- Create a function named findSmallestNumberPossible that takes two integer parameters N and K.
- If N is greater than the maximum possible sum of digits (K * 45), output -1 as it is impossible to form such a number. Otherwise, continue.
- Create an integer array freq with size 10 to store the frequency of each digit.
- Create an empty string res to store the result.
- Initialize the sum of digits sum to 0.
- Iterate over the digits from 9 to 0 using a for loop.
- While the frequency of digit i is less than K and the sum of digits is less than or equal to N, do the following:
a. Increment the frequency of digit i.
b. Add digit i to the front of the result string res.
c. Update the sum of digits sum by adding i. - Remove leading zeros from the result string by iterating over it and counting the number of zeros at the beginning.
- If the result string contains only zeros, output 0. Otherwise, output the result string without leading zeros.
Below is the implementation of the above approach:
C++
#include <iostream> #include <string> using namespace std; // Function to find the smallest number whose sum of digits is N // and every distinct digit in that number occurs at most K times. void findSmallestNumberPossible( int N, int K) { // If N is greater than the maximum possible sum, // return -1 as it is impossible to form such a number if (N > K * 45) { cout << "-1" << endl; return ; } // Create an array to store the frequency of each digit int freq[10] = {0}; // Create an empty string to store the result string res = "" ; // Initialize the sum of digits to 0 int sum = 0; // Iterate over the digits from 9 to 0 for ( int i = 9; i >= 0; i--) { // While the frequency of digit i is less than K // and the sum of digits is less than or equal to N while (freq[i] < K && sum + i <= N) { // Increment the frequency of digit i freq[i]++; // Add digit i to the front of the result string res = ( char )( '0' + i) + res; // Update the sum of digits sum += i; } } // Remove leading zeros from the result string int zeros = 0; while (zeros < res.length() && res[zeros] == '0' ) { zeros++; } // If the result string contains only zeros, output 0 if (zeros == res.length()) { cout << "0" << endl; } else { // Otherwise, output the result string without leading zeros cout << res.substr(zeros) << endl; } } int main() { int N = 25, K = 3; findSmallestNumberPossible(N, K); // Output: 799 return 0; } // This code is contributed by rudra1807raj |
Java
import java.util.Arrays; public class SmallestNumberPossible { // Function to find the smallest number whose sum of digits is N // and every distinct digit in that number occurs at most K times. public static void findSmallestNumberPossible( int N, int K) { // If N is greater than the maximum possible sum, // return -1 as it is impossible to form such a number if (N > K * 45 ) { System.out.println( "-1" ); return ; } // Create an array to store the frequency of each digit int [] freq = new int [ 10 ]; Arrays.fill(freq, 0 ); // Create an empty string to store the result StringBuilder res = new StringBuilder( "" ); // Initialize the sum of digits to 0 int sum = 0 ; // Iterate over the digits from 9 to 0 for ( int i = 9 ; i >= 0 ; i--) { // While the frequency of digit i is less than K // and the sum of digits is less than or equal to N while (freq[i] < K && sum + i <= N) { // Increment the frequency of digit i freq[i]++; // Add digit i to the front of the result string res.insert( 0 , i); // Update the sum of digits sum += i; } } // Remove leading zeros from the result string int zeros = 0 ; while (zeros < res.length() && res.charAt(zeros) == '0' ) { zeros++; } // If the result string contains only zeros, output 0 if (zeros == res.length()) { System.out.println( "0" ); } else { // Otherwise, output the result string without leading zeros System.out.println(res.substring(zeros)); } } public static void main(String[] args) { int N = 25 , K = 3 ; findSmallestNumberPossible(N, K); // Output: 799 } } // This code is contributed by rudra1807raj |
Python3
def find_smallest_number_possible(N, K): # If N is greater than the maximum possible sum, # return -1 as it is impossible to form such a number if N > K * 45 : print ( "-1" ) return # Create a list to store the frequency of each digit freq = [ 0 ] * 10 # Create an empty string to store the result res = "" # Initialize the sum of digits to 0 sum_digits = 0 # Iterate over the digits from 9 to 0 for i in range ( 9 , - 1 , - 1 ): # While the frequency of digit i is less than K # and the sum of digits is less than or equal to N while freq[i] < K and sum_digits + i < = N: # Increment the frequency of digit i freq[i] + = 1 # Add digit i to the front of the result string res = str (i) + res # Update the sum of digits sum_digits + = i # Remove leading zeros from the result string zeros = 0 while zeros < len (res) and res[zeros] = = '0' : zeros + = 1 # If the result string contains only zeros, output 0 if zeros = = len (res): print ( "0" ) else : # Otherwise, output the result string without leading zeros print (res[zeros:]) # Driver code if __name__ = = "__main__" : N = 25 K = 3 find_smallest_number_possible(N, K) # Output: 799 |
C#
using System; public class GFG { // Function to find the smallest number whose sum of // digits is N and every distinct digit in that number // occurs at most K times. static void FindSmallestNumberPossible( int N, int K) { // If N is greater than the maximum possible sum, // return -1 as it is impossible to form such a // number if (N > K * 45) { Console.WriteLine( "-1" ); return ; } // Create an array to store the frequency of each // digit int [] freq = new int [10]; // Create an empty string to store the result string res = "" ; // Initialize the sum of digits to 0 int sum = 0; // Iterate over the digits from 9 to 0 for ( int i = 9; i >= 0; i--) { // While the frequency of digit i is less than K // and the sum of digits is less than or equal // to N while (freq[i] < K && sum + i <= N) { // Increment the frequency of digit i freq[i]++; // Add digit i to the front of the result // string res = i.ToString() + res; // Update the sum of digits sum += i; } } // Remove leading zeros from the result string int zeros = 0; while (zeros < res.Length && res[zeros] == '0' ) { zeros++; } // If the result string contains only zeros, output // 0 if (zeros == res.Length) { Console.WriteLine( "0" ); } else { // Otherwise, output the result string without // leading zeros Console.WriteLine(res.Substring(zeros)); } } public static void Main( string [] args) { int N = 25, K = 3; FindSmallestNumberPossible(N, K); } } |
Javascript
// Function to find the smallest number whose sum of digits is N // and every distinct digit in that number occurs at most K times. function findSmallestNumberPossible(N, K) { // If N is greater than the maximum possible sum, // return -1 as it is impossible to form such a number if (N > K * 45) { console.log( "-1" ); return ; } // Create an array to store the frequency of each digit let freq = new Array(10).fill(0); // Create an empty string to store the result let res = "" ; // Initialize the sum of digits to 0 let sum = 0; // Iterate over the digits from 9 to 0 for (let i = 9; i >= 0; i--) { // While the frequency of digit i is less than K // and the sum of digits is less than or equal to N while (freq[i] < K && sum + i <= N) { // Increment the frequency of digit i freq[i]++; // Add digit i to the front of the result string res = i + res; // Update the sum of digits sum += i; } } // Remove leading zeros from the result string let zeros = 0; while (zeros < res.length && res.charAt(zeros) === '0' ) { zeros++; } // If the result string contains only zeros, output 0 if (zeros === res.length) { console.log( "0" ); } else { // Otherwise, output the result string without leading zeros console.log(res.substring(zeros)); } } // Test the function let N = 25, K = 3; findSmallestNumberPossible(N, K); // Output: 799 |
799
Time Complexity: The time complexity of this code is O(10K), where K is the maximum frequency of each digit. This is because the loop iterates over the digits from 9 to 0 at most 10 times, and for each digit, the while loop runs at most K times.
Auxiliary Space: The space complexity of this code is O(K), which is the size of the freq array used to store the frequency of each digit. The size of the res string is also O(K) because it can have at most K digits. Therefore, the overall space complexity of the code is O(K).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!