Hi all. I just sat for a coding test with a company and came across this question.

The logic I thought of turned out to be quite a jumbled mess of logic.
I do believe that there is a much simpler solution to this than what I thought of.
Will appreciate if someone could help me out with this.

Question
You are given a number N. A number is called beautiful if for every digit x in the number there are x occurrences of it in the number.

1 is beautiful because 1 has 1 occurrence
3133 is beautiful because 1 has 1 occurence and 3 has 3 occurences
224 is not beautiful

Determine the smallest beautiful number which is greater than N.

eg. N=1 ans: 22 is the smallest beautiful number greater than 1
N=250 ans: 333

Constraints: 1<N<10^12

Brute Force
Go through each and every number starting from current number till a beautiful number is found.

Another Approach
One approach that came to mind was rather than going through each and every number, I can first of all, limit the search space by calculating the number of digits in the given number and just finding all possible beautiful numbers with length n and n+1.

Now to achieve this, One thing I noticed is that each number of length n digits is only composed of the digits which when taken only once, sum up to n ;
For example
8 = 1+2+5;
or 8 = 4+3+1;
....
So 88888888 can be broken into 12255555 or 44443331 and all their permutations.

Thus it basically becomes a variation of subset sum problem for number n from set 1 to 9 which would be precomputed in O(10*10);.

Also I believe it can further be optimized by taking into consideration the first digit of the number. If say the digit is x, thus our first digit has to be either x or digit greater than x, and for every such group which satisfies our constraint, we fix the first digit and then we try to generate the numbers in lexicographical order and for every group calculate every such number which is just greater.

Thank You in advance for any insight.