Nth Natural Number

Given a positive integer n. You have to find n^th natural number after removing all the numbers containing the digit 9.

Examples :

Input: n = 8
Output: 8
Explanation: After removing natural numbers which contains digit 9, first 8 numbers are 1,2,3,4,5,6,7,8 and 8th number is 8.

Input: n = 9
Output: 10
Explanation: After removing natural numbers which contains digit 9, first 9 numbers are 1,2,3,4,5,6,7,8,10 and 9th number is 10.

Expected Time Complexity: O(logn)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ n ≤ 10⁹

Approach 01:

#include <iostream>

class Solution {
public:
    long long findNth(long long N) {
        // Base-9 conversion to skip numbers containing '9'
        return base9ToSkipNine(N);
    }

private:
    long long base9ToSkipNine(long long number) {
        long long base9Number = 0;
        long long multiplier = 1;
        while (number > 0) {
            base9Number += (number % 9) * multiplier;
            number /= 9;
            multiplier *= 10;
        }
        return base9Number;
    }
};

class Solution:

    def findNth(self, N):
        # Base-9 conversion to skip numbers containing '9'
        return self.base9ToSkipNine(N)
        
    def base9ToSkipNine(self, number):
        base9Number = 0
        multiplier = 1
        while number > 0:
            base9Number += (number % 9) * multiplier
            number //= 9
            multiplier *= 10
        return base9Number

Time Complexity

• Base-9 Conversion:

  The function base9ToSkipNine performs a while loop that iterates until number becomes zero. In each iteration, the number is divided by 9, which reduces the size of the number logarithmically. Thus, the number of iterations is proportional to the logarithm of the input number with base 9. The time complexity of this conversion is \( O(\log_{9} N) \), which simplifies to \( O(\log N) \) because the base of the logarithm does not affect the asymptotic complexity.

• Overall Time Complexity:

  The overall time complexity of the function is \( O(\log N) \).

Space Complexity

• Auxiliary Space:

  The function uses a few variables (base9Number, multiplier) for intermediate calculations. The space required for these variables is constant, so the auxiliary space complexity is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).