Nth Natural Number

JavaView on GFG

Problem Overview

Find nth natural number that does not contain digit 9.

Intuition

Find nth natural number that does not contain digit 9. Treat remaining digits 0-8 as base-9 number system.

Algorithm

1Convert n to base 9. Map each digit 0-8 to digits 0-8 (no 9). That gives the nth number.

Common Pitfalls

• Base-9 conversion: digits 0,1,2,...,8 map directly. Digit 9 is never used. n in base 9 gives the answer.

Nth Natural Number.java

Java

// Approach: Skip numbers containing digit 9 (since we use base-9 style counting). Convert position to base-9.
// Time: O(log n) Space: O(1)
class Solution {
    long findNth(long n) {
        if (n < 9)
            return n;

        return findNth(n / 9) * 10 + n % 9;
    }
}

Was this solution helpful?