Dare2Solve
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.
The numbers are concatenated together into an infinite string. The key observation is that numbers have different lengths:
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.
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:
n
can be found within that range.n
and move to the next range.n
falls into a specific range.Once the range is found, calculate which number contains the Nth digit:
(n-1) / digitInNum
to determine the exact number.(n-1) % digitInNum
.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
.
O(1)
. We only use a few variables to track the state of the problem.
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';
}
};
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])
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';
}
}
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];
};