my solution of Tidy Number (Google Code Jam)

Comments

[Long Tran]

But what if the testcase is like 11110, the decreasing character is at index 3. Follow your solution then we have 11109 (not a tidy number, the correct answer is 9999). It seems that after decreasing the left part by 1, we also need to check those digits stand before the decreasing character again.

[Lorenzo Mele]

You are perfectly right!

I just updated the gist with the fix (I forgot to make solve() recursive, that's the key!).

[Long Tran]

Btw, base on your idea then I found out a solution (edit a little bit):
We need to store the index of the first appearance of decreasing character, for example:

• 11110 ( the decreasing character is '1', but we need to store the index of the first time appearance of it in the number, the index here is number 0).
• 12344296 ( the decreasing character is '4' and we store the index of its first appearance, is 3) Finally, we split the origin in 3 parts: ( assume our digits testcase right now is 12344296)
• Firstly, the starting digits are digits.substring(0, indexAbove) -- 123
• Secondly, only 1 digit in which value decreases by 1. -- 3
• Finally, the latter part is 9999, you can concat the result to the number which equals to 10** (digits.length - indexAbove) - 1 , ** is power operator. Thank you for reading my idea.

[Long Tran]

Your recursive solution is coded beautifully and easy to understand, thanks a lot!

[Frederik 👨‍💻➡️🌐 Creemers]

Especially for the qualification round, where you have more time, I like the idea of your brute force algorithm as a unit test.

[Lorenzo Mele]

Thanks!
Indeed this is not a good solution for the next rounds, even if it could help you understand the problem.