algoadvance

Leetcode 400. Nth Digit

Problem Statement

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Clarifying Questions

1. What is the size range of n?
   • n is a positive integer and can be very large, within the range [1, 2^31 - 1].
2. Is there any built-in function usage restriction?
   • Typically, no specific restriction on built-in functions unless mentioned.
3. Should the output be a digit (0-9)?
   • Yes, the result for nth digit will always be a single digit from 0 to 9.

Strategy

1. Understand the distribution of digits:
   • Numbers 1-9 contribute 9 digits.
   • Numbers 10-99 contribute 180 digits.
   • Numbers 100-999 contribute 2700 digits.
   • In general, numbers with d digits contribute d * 9 * (10^(d-1)) digits.
2. Break the Problem in Steps:
   • Determine the range of numbers where the nth digit falls.
   • Find the exact number and digit position within that number.

Code

#include <iostream>
#include <cmath>

class Solution {
public:
    int findNthDigit(int n) {
        long long len = 1; // number of digits in the current number range
        long long count = 9;
        long long start = 1;

        // Determine the range where the nth digit is
        while (n > len * count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        
        // Find the exact number and the digit position
        start += (n - 1) / len;
        std::string num = std::to_string(start);
        return num[(n - 1) % len] - '0'; // Access the exact digit and convert to integer
    }
};

int main() {
    Solution solution;
    int n = 400;
    std::cout << solution.findNthDigit(n) << std::endl; // Output for the given example
    return 0;
}

Time Complexity

• Time Complexity: O(log n)
  • The loop where we determine the length of digits takes logarithmic time because for each digit length increase, the range increases by a factor of 10.
  • Converting a number to string and accessing a digit takes constant time because we are only performing a few operations for each individual length.
• Space Complexity: O(1)
  • Only a few extra variables are used regardless of the size of n. The space used for conversion to a string and accessing a character is also constant.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?