
Description
The problem is to find the Nth digit in an infinite sequence of numbers, where all numbers are concatenated in order. For example, for n = 11
, the sequence would look like 123456789101112...
, and the 11th digit is 0
from 10
.
Given an integer n
, the goal is to return the Nth digit of the sequence.
Intuition
The numbers are concatenated together into an infinite string. The key observation is that numbers have different lengths:
- Single-digit numbers: 1 to 9 (9 digits).
- Two-digit numbers: 10 to 99 (180 digits).
- Three-digit numbers: 100 to 999 (2700 digits).
The idea is to determine which range the n
th digit belongs to by adjusting the value of n
. Once we find the range, we compute the exact number that contains the Nth digit and return the digit.
Approach
- Initialize the variables to represent:
-
digitInNum
: the current number of digits in the range. -start
: the starting number of the current range. -end
: the total number of digits in the current range. - Traverse through the number ranges:
- For each range of digits, check if
n
can be found within that range. - Subtract the number of digits in the current range fromn
and move to the next range. - Continue untiln
falls into a specific range. - Once the range is found, calculate which number contains the Nth digit:
- Use
(n-1) / digitInNum
to determine the exact number. - Convert the number to a string and return the correct digit using(n-1) % digitInNum
.
Complexity
Time Complexity:
O(log n)
. The while loop reduces n
based on the number of digits in the range. Since the number of digits increases exponentially, the loop runs in logarithmic time relative to n
.
Space Complexity:
O(1)
. We only use a few variables to track the state of the problem.
Code
C++
class Solution {
public:
int findNthDigit(int n) {
long digitInNum = 1, start = 1, end = 9;
while (n > digitInNum * end) {
n -= digitInNum * end;
digitInNum++;
start *= 10;
end *= 10;
}
long num = start + (n - 1) / digitInNum;
string numStr = to_string(num);
return numStr[(n - 1) % digitInNum] - '0';
}
};
Python
class Solution:
def findNthDigit(self, n: int) -> int:
digit_in_num = 1
start = 1
end = 9
while n > digit_in_num * end:
n -= digit_in_num * end
digit_in_num += 1
start *= 10
end *= 10
num = start + (n - 1) // digit_in_num
return int(str(num)[(n - 1) % digit_in_num])
Java
class Solution {
public int findNthDigit(int n) {
long digitInNum = 1, start = 1, end = 9;
while (n > digitInNum * end) {
n -= digitInNum * end;
digitInNum++;
start *= 10;
end *= 10;
}
long num = start + (n - 1) / digitInNum;
String numStr = Long.toString(num);
return numStr.charAt((int) ((n - 1) % digitInNum)) - '0';
}
}
JavaScript
var findNthDigit = function (n) {
let digitInNum = 1;
let start = 1;
let end = 9;
while (n > (digitInNum * end)) {
n = n - digitInNum * end;
digitInNum++;
start = start * 10;
end = end * 10;
}
let num = start + Math.floor((n - 1) / digitInNum);
num = num.toString();
return num[(n - 1) % digitInNum];
};