# 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…

My solution using backtracking: https://www.codechef.com/viewsolution/27732112

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

4 Likes

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

2 Likes

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.

eg:
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.

4 Likes

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

4 Likes

Beautiful solution brother👌

3 Likes

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