How to solve Smallest Beautiful Number (LSTBTF)?

I know the editorial will be uploaded soon, but my dad is eager to know the solution.
If you’ve solved it, just give me a rough idea of how to solve it…
Thanks in advance :slight_smile:

My solution using backtracking:

Basic idea is to check all possibilities such that all numbers are in non decreasing order.


Very rough Idea, A recursive brute force solution with a little optimization is enough to pass all test cases.

1 Like

Can u plz elaborate your solution with some example plz

There is no need to check of 121 if 112 already checked , and so on


This is similar to standard backtracking problems.

For every position i am placing a number (say x) and asking the function (canplace()) if it’s the correct number. If it is, return 1.

If it’s not we backtrack and place the next number (x+1) (hence the for loop) and do the same again.

“prev” is necessary so that we always have a non decreasing sequence.

for 5
1 1 1 1 1 ,
1 1 1 1 2 ,

1 1 1 1 9,
1 1 1 2 2,
1 1 1 2 3, …
and so on.

Hope you got the basic idea.


Cool, i had thought this up, but couldn’t write code for it, and the idea died a premature death…lol happens a lot with me


Beautiful solution brother👌


Use dynamic programming to create a lookup table and then use it to calculate the answer.

Follow solution

1 Like

I am guessing this is a brute force with a lookup to speed up right?

Yeah since difference the provided number N, to the nearest perfect square number is atmost 2002 when N=999999, so creating a lookup table with DP, and then brute forcing for each number to calculate the result, this works way faster than the backtracking solution.

Yup, optimized brute force so to speak

can someone please make a video solution.

1 Like