Smallest number whose sum of digits is N and every digit occurring at most K times | C ++ 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 ; Maximum sum possible using each digit at most K times ; Append smallest number into the resultant string ; Iterate over the range [ 9 , 1 ] ; If the count of the digit is K , then update count and check for the next digit ; If N is greater than current digit ; Subtract i from N ; Insert i as a digit ; Insert remaining N as a digit ; Increment count ; Reverse the string ; Print the answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findSmallestNumberPossible ( int N , int K ) { if ( N > 45 * K ) { cout << " - 1" ; return ; } string res = " " ; int count = 0 ; for ( int i = 9 ; i >= 1 ; ) { if ( count == K ) { i -- ; count = 0 ; } if ( N > i ) { N -= i ; res += ( char ) 48 + i ; } else { res += ( char ) N + 48 ; N = 0 ; break ; } count ++ ; } reverse ( res . begin ( ) , res . end ( ) ) ; cout << res ; } int main ( ) { int N = 25 , K = 3 ; findSmallestNumberPossible ( N , K ) ; return 0 ; }