Nth Natural Number

JavaView on GFG

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?