Smallest Beautiful Number(LSTBTF)?

anon52057592 · November 11, 2019, 3:29pm

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

s5960r · November 11, 2019, 3:44pm

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

anon8049083 · November 11, 2019, 5:36pm

@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 )

anon8049083 · November 11, 2019, 5:44pm

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

s5960r · November 11, 2019, 5:50pm

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

anon8049083 · November 11, 2019, 6:12pm

Yea , i’m waiting for that : )

maghav12 · November 11, 2019, 6:22pm

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?