# Smallest Beautiful Number(LSTBTF)?

Can anybody please help me with the logic of this problem. I tried to do it as coin change problem having denominations of n^2 - 1.
Please provide the logic and not the code

Letās say we are working on any given n

The number will have n digits.

Now the digits can only be 1,2,3,4,5,6,7,8,9

Letās say number x is our required number.
x will have these digits in some amount/count.

Say count of every digit d is count[d]

and if the number is smallest beautiful number then the quantity

1^2 *count[1] + 2^2 * count[2] ....9^2 * count[9]

should be a perfect square and sum of total counts should be n

we already know the values for 1^2, 2^2ā¦9^2

All we need to work with is count of each digit.

So start from count of smallest digit i.e 1 and use 9 nested loops to distribute the counts.
and check for each configuration.
the first valid configuration will the answer

7 Likes

@s5960r how did you convince that this system is always consistent ? (i.e, not a " -1 ")
I thought of Bachetās conjecture but I didnāt convince for natural numbers .
( every number can be and hence squares , but it includes zeroes )

I have written the same equations on my scratchpad and thought of implementing , but thinking about inconsistency and time complexity ruined my idea

1 Like

Iāll be honest and i actually didnāt āthinkā instead i āobservedā. There were no -1 for first n<=100 , so i concluded thatš.

Btw Iām curious if thereās a mathematical proofš¤

Letās see what editorial has to offer

1 Like

Yea , iām waiting for that : )

Hi @s5960r, as the digits can have a maximum value of 10^6, how does running 9 nested loops fit in the time complexity constraints?