The problem statement is straight-forward: you've a number sequence without 9s, and given an index, you've to return value at that position in the sequence.
You can begin with a brute force solution. Given an index n:
- Declare a counter c with 1 as initial value
- Loop 1 to n
- Increment c by 1
- If c has digit 9, jump to previous step
For testing if c has 9, you can convert c to a string and look for character '9'. However, this approach fails for n > 2.5 x 10^6 approx. (memory limit exceeded)
Converting a number to string every time and then doing a character by character doesn't sound very efficient. Can you think of a better implementation for has9()?
There is a way you can numerically find out existence of digit 9 in a number:
- let x = n
- while x > 0
- let d = x % 10 // Read right most digit in x
- if d is 9, return true
- x = Math.floor(x / 10) // Remove right most digit in x
- return false
This approach adds a little bit of improvement, but it fails beyond n > 1 x 10 ^ 7 approx. (time limit exceeded)
We're still lagging way behind than the target goal of reaching n = 9 x 10 ^ 8. Improving has9() function gave us 4x improvement, but we still need 90x improvement.
There isn't much we can do around has9() function. Can you improve the primary while loop (the one mentioned in first iteration section)? Is there any way we can make an equation out of it?
You might be thinking that you can make a mathematical equation for it. Go ahead and plot an input/output sequence. It might look like this:
Notice that initially till number 8, both sequences go the same. After 8, we skip a number and jump to 10 (in f(n) row). Now f(n) is 1 number ahead of input sequence. At input 18, we skip another number and jump to 20. Now f(n) is 2 numbers ahead of input sequence. Next, we skip another at input 27 and jump to 30. Now f(n) is 3 numbers ahead of input sequence.
At every multiple of 9, f(n) gets bumped by 1.
This relationship can be written like this:
Or like this:
Do you see what I see? :)
This turns out to be a number system problem. You've to convert a base 10 number to a base 9 number. This is similar to converting a base 10 number to a base 2 number that most of us are already familiar with. Apply the same technique here and you've got your solution.