loading...

Posted on by:

greenkey profile

Lorenzo Mele

@greenkey

Life is short. A bio is too short to describe even a part of it.

Discussion

pic
Editor guide
 

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.

 

You are perfectly right!

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

 

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.
 

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

 

I tried an implementation too:
gist.github.com/fcalderan/fccca9df...

To check if a number is tidy I've just compared if its array-split representation is equivalent to the same array sorted ascending.

So if my number was 1978 then in python I would check if [1,9,7,8] == sorted([1,9,7,8])

 

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

 

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