Nth Digit — Solution in Python, Java & C++
Nth Digit solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Nth Digit is a medium coding problem on math and binary search, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Math, Binary Search
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Consider the infinite sequence formed by writing the positive integers one after another: 123456789101112…
Given an integer n, return the n-th digit of that sequence (1-indexed).
Example 1
Input: n = 3
Output: 3
Example 2
Input: n = 11
Output: 0
Explanation: The 11th digit falls inside 10.
Example 3
Input: n = 1000000000
Output: 1
Constraints
1 <= n <= 2147483647
Hints for Nth Digit
Hint 1
There are 9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, and so on.
Hint 2
Subtract those blocks from
nuntil it lands inside the block ofd-digit numbers.Hint 3
Then integer division pinpoints the number and the remainder pinpoints the digit inside it — use 64-bit arithmetic so the block sizes do not overflow.
How to solve Nth Digit
Skip whole blocks — 9 one-digit numbers, 90 two-digit, 900 three-digit — until n lands in the block of d-digit numbers, then locate the number and the digit within it.
Approach
- While
n > digits · count: subtract, thendigits++,count *= 10,start *= 10. value = start + (n - 1) // digits; return digit(n - 1) % digitsofvalue.
Why it works
Digit positions are consecutive across the numbers of a block, so integer division by the block's digit width maps the offset to a number and the remainder to a digit.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- Use 64-bit arithmetic for
digits · count.
Reference solution
Python
def findNthDigit(n: int) -> int:
digits = 1
count = 9
start = 1
while n > digits * count:
n -= digits * count
digits += 1
count *= 10
start *= 10
value = start + (n - 1) // digits
return int(str(value)[(n - 1) % digits])Java
public static int findNthDigit(int n) {
long remaining = n;
long digits = 1;
long count = 9;
long start = 1;
while (remaining > digits * count) {
remaining -= digits * count;
digits++;
count *= 10;
start *= 10;
}
long value = start + (remaining - 1) / digits;
String text = String.valueOf(value);
return text.charAt((int) ((remaining - 1) % digits)) - '0';
}C++
int findNthDigit(int n) {
long long remaining = n, digits = 1, count = 9, start = 1;
while (remaining > digits * count) {
remaining -= digits * count;
digits++;
count *= 10;
start *= 10;
}
long long value = start + (remaining - 1) / digits;
string text = to_string(value);
return text[(int) ((remaining - 1) % digits)] - '0';
}JavaScript
var findNthDigit = function(n) {
let remaining = n;
let digits = 1;
let count = 9;
let start = 1;
while (remaining > digits * count) {
remaining -= digits * count;
digits++;
count *= 10;
start *= 10;
}
const value = start + Math.floor((remaining - 1) / digits);
const text = String(value);
return Number(text.charAt((remaining - 1) % digits));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search