Problem can be easily solved using the solution to standard COIN CHANGE PROBLEM.
Suppose you are given a number N.
Now consider a base answer that is a string of size N only containing 1.
So there are two cases:
Case 1: N is a perfect square. You can print the base answer directly.
Case 2:N is not a perfect square.
Now let’s solve Case 2, as N is not a perfect square , we’ll have to replace some 1s in the base answer with other digits from 2 to 9, and this will obviously result in increment of our base answer’s value. So now there are only 8 kinds of possible changes to the sum you can make and they are 3,8,15,24,35,48,63 and 80 i.e. if you replace a 1 with 2 then net change is of 2^2 - 1 = 3. So let’s think these 8 changes are the 8 kind of coins we have and we can use any coin more than once to create the required sum, which is same as the problem statement of COIN CHANGE PROBLEM.
I’m not delving into the solution of coin change problem, you can find it anywhere, but now the only remaining question is that how do we know what the required sum is. So you must keep in mind that minimum square for any N will be N itself (where every digit will be 1) and obviously maximum answer will be 81*N (where every digit will be 9). So we have to start from our base answer find the next perfect square then find if we can make the change using given coins, if not process next perfect square, if yes then see if the solution is lexicographically smallest answer we have found yet.
As one common mistake someone might make at this juncture is minimizing the square sum, which is not required. We have to just find the smallest beautiful number not the number with smallest square sum. For example answer for N = 18 is 111111111111111118 but it’s square sum is 81 and 111111111111111124 has square sum 36, so answer should be 111111111111111118 even if the square sum is greater.
My Solution