Step By Step Solution


  • 0
    U

    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.

    First Iteration

    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()?

    Second Iteration

    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?

    Third Iteration

    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:

    0_1504632830777_Screen Shot 2017-09-05 at 10.32.17 PM copy.jpg

    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.

    0_1504633502542_Screen Shot 2017-09-05 at 10.32.09 PM copy.jpg

    This relationship can be written like this:

    0_1504633642663_Screen Shot 2017-09-05 at 10.31.54 PM.png

    Or like this:

    0_1504633683146_Screen Shot 2017-09-05 at 10.31.58 PM.png

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.