Nth Digit solution and explanation
Google
9 more videos on this problem
LeetCode 400. Nth DigitHappy Coding · 11:20 · 10K views
Leetcode 400. Nth DigitJie Zhou · 6:01 · 4K views
LEETCODE-400|Nth digitRishabh Maheshwari · 14:28 · 1K views
400. Nth Digit (Leetcode Medium)Programming Live with Larry · 13:28 · 1K views
400. Nth Digit | Leetcode | MetaHimani · 17:34 · 856 views
LeetCode 400: Find Nth Digit | Math + Binary Search Intuition | C++ Optimized 🔢Ctrl Alt Success · 22:37 · 666 views
Nth Digit | Leetcode 400 | Approach + Code with explanation.Pirai's Academy · 18:55 · 531 views
Leetcode 400. Nth Digit (math)LetsCode · 9:33 · 297 views
400. Nth DigitJust Coding, with Jie · 14:10 · 280 views
LeetCode_400 : Nth DigitQianqiu Xin · 12:58 · 208 views
The problem
Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
Example 1:
Input: n = 3 Output: 3
Example 2:
Input: n = 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
Constraints:
1 <= n <= 231 - 1
Approach overview
Problem Overview: You are given an integer n and must return the nth digit in the infinite sequence 123456789101112.... The sequence is formed by concatenating all positive integers. The challenge is locating which number and which digit inside that number corresponds to position n.
Approach 1: Counting Digits in Blocks (O(log n) time, O(1) space)
Numbers contribute digits in predictable blocks. All 1‑digit numbers (1–9) contribute 9 * 1 digits. Two‑digit numbers (10–99) contribute 90 * 2 digits. Three‑digit numbers contribute 900 * 3, and so on. Iterate through these blocks while subtracting their total digit contribution from n until the remaining value falls inside a specific digit-length group. Once the correct block is found, compute the exact number using division and locate the target digit using modulo indexing. This approach relies on simple arithmetic and iteration over digit ranges, making it a clean application of math reasoning.
Approach 2: Mathematical Calculation (O(log n) time, O(1) space)
This version performs the same block reasoning but formulates the calculations more directly. First determine the digit length d where the nth digit resides by subtracting blocks of size 9 * 10^(d-1) * d. Once identified, compute the exact number using start = 10^(d-1) and number = start + (n-1) / d. The desired digit index is (n-1) % d within that number. Because each step eliminates an entire digit range, the loop runs only for the number of digit lengths (at most ~10 for 32‑bit inputs). Some implementations also model the search for the correct block using binary search, but direct arithmetic is typically simpler.
Recommended for interviews: The mathematical block-counting approach is what interviewers expect. It shows that you recognize the structure of the sequence and avoid brute-force concatenation. A naive solution that actually builds the string grows too slowly and uses unnecessary memory, while the optimal math approach finds the digit in logarithmic time with constant space.
Approach 1: Counting Digits in Blocks
In this approach, we'll handle the problem by counting how many digits are in the sequence up to the point we reach our desired digit. We'll divide the sequence into blocks of digits. The first block consists of single-digit numbers, the next contains two-digit numbers, and so on.
- Initiate an integer variable to store the current block size, and another integer to accumulate how many digits have been counted so far.
- Iterate the sequence of numbers by blocks (e.g., single digits, double digits, etc.), calculating how many digits each block consumes.
- Once you find the block that contains the nth digit, determine the specific number and which digit within it is needed.
- Finally, return the identified digit.
def findNthDigit(n: int) -> int:
digit_length = 1
count = 9
while n > digit_length * count:
n -= digit_length * count
digit_length += 1
count *= 10
index = n - 1
start = 10 ** (digit_length - 1)
num = start + index // digit_length
digit_index = index % digit_length
return int(str(num)[digit_index])function findNthDigit(n) {
let digitLength = 1;
let count = 9;
while (n > digitLength * count) {
n -= digitLength * count;
digitLength++;
count *= 10;
}
let index = n - 1;
let start = Math.pow(10, digitLength - 1);
let num = start + Math.floor(index / digitLength);
let digitIndex = index % digitLength;
return parseInt(String(num)[digitIndex]);
}This Python function identifies which digit corresponds to the nth number in a simulated infinite sequence of integers. By calculating the block of numbers and indexing into the correct position, you can efficiently pinpoint the desired digit.
Time Complexity: O(log n), since the number of digits in numbers grows logarithmically.
Space Complexity: O(1), constant space usage besides inputs and counters.
Approach 2: Mathematical Calculation
This approach relies on recognizing the pattern and position of numbers within blocks without iterative counting. It calculates the digit using arithmetic operations and modularity. Assume a number format and work towards the digit by shifting through their positions mathematically.
- Determine the size of the number based on the digit length required.
- Calculate which number contains the needed
nthdigit. - Directly access and return the specific digit from the number by translating
nindex to digit index.
class Solution {
public int findNthDigit(int n) {
int digitLength = 1;
long count = 9;
while (n > digitLength * count) {
n -= digitLength * count;
digitLength++;
count *= 10;
}
int start = (int) Math.pow(10, digitLength - 1);
int num = start + (n - 1) / digitLength;
return Integer.toString(num).charAt((n - 1) % digitLength) - '0';
}
}#include <iostream>
#include <string>
using namespace std;
int findNthDigit(int n) {
long digit_length = 1, count = 9;
while (n > digit_length * count) {
n -= digit_length * count;
digit_length++;
count *= 10;
}
int index = n - 1, start = pow(10, digit_length - 1);
int num = start + index / digit_length;
string numStr = to_string(num);
return numStr[index % digit_length] - '0';
}The Java approach uses basic math shifting to bypass full sequence enumeration. By selectively stepping through digit sizes and applying the necessary index arithmetic, it resolves the solution from scenario to outcome quickly.
Time Complexity: O(log n), based on the required operations regarding digit categorization.
Space Complexity: O(1), due to tracking with constant space sparse of state manipulation.
Approach 3: Mathematics
The smallest and largest integers with k digits are 10^{k-1} and 10^k-1 respectively, so the total number of digits for k-digit numbers is k times 9 times 10^{k-1}.
We use k to represent the number of digits of the current number, and cnt to represent the total number of numbers with the current number of digits. Initially, k=1, cnt=9.
Each time we subtract cnt times k from n, when n is less than or equal to cnt times k, it means that the number corresponding to n is within the range of numbers with the current number of digits. At this time, we can calculate the corresponding number.
The specific method is to first calculate which number of the current number of digits corresponds to n, and then calculate which digit of this number it is, so as to get the number on this digit.
The time complexity is O(log_{10} n).
public class Solution {
public int FindNthDigit(int n) {
int k = 1, cnt = 9;
while ((long) k * cnt < n) {
n -= k * cnt;
++k;
cnt *= 10;
}
int num = (int) Math.Pow(10, k - 1) + (n - 1) / k;
int idx = (n - 1) % k;
return num.ToString()[idx] - '0';
}
}func findNthDigit(n int) int {
k, cnt := 1, 9
for k*cnt < n {
n -= k * cnt
k++
cnt *= 10
}
num := int(math.Pow10(k-1)) + (n-1)/k
idx := (n - 1) % k
return int(strconv.Itoa(num)[idx] - '0')
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Digits in Blocks | Time Complexity: O(log n), since the number of digits in numbers grows logarithmically. |
| Mathematical Calculation | Time Complexity: O(log n), based on the required operations regarding digit categorization. |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Digits in Blocks | O(log n) | O(1) | Best general approach. Easy to reason about by iterating through digit ranges. |
| Mathematical Calculation | O(log n) | O(1) | Preferred in interviews for concise arithmetic solution. |
| Binary Search on Digit Ranges | O(log n) | O(1) | Useful if modeling the problem as searching for the number whose digit span contains n. |
Frequently asked questions
Is Nth Digit easy or hard?
Nth Digit is typically rated Medium because the implementation is short but the insight about digit blocks is not immediately obvious. Once the pattern of 1-digit, 2-digit, and 3-digit ranges is recognized, the solution becomes straightforward.
How to solve Nth Digit in O(log n)?
First determine the digit length group where the nth digit lies by subtracting digit blocks such as 9×1, 90×2, 900×3. After identifying the block, compute the target number with start + (n−1)/digits and find the digit index using (n−1)%digits. Extract the digit from the resulting number.
What is the best approach for Nth Digit?
The optimal approach counts digits in number-length blocks (1-digit, 2-digit, 3-digit, etc.). Subtract each block's total digit contribution until the remaining index falls within a block, then compute the exact number and digit using division and modulo. This runs in O(log n) time with O(1) space.
What data structure is used in Nth Digit?
No special data structures are required. The solution relies on arithmetic operations and integer math to identify the correct digit block and extract the target digit.
What is the time complexity of Nth Digit?
The standard solution runs in O(log n) time and O(1) space. The loop iterates through digit lengths (1-digit, 2-digit, 3-digit...), which grows logarithmically relative to n. No large strings or arrays are created.
Nth Digit Python or Java solution approach?
Both Python and Java implementations follow the same math logic: determine the digit-length block, compute the actual number containing the digit, and index into it. Python often converts the number to a string for extraction, while Java may use arithmetic or string conversion.
Is Nth Digit asked at Google, Amazon, or Meta?
Variants of digit indexing and number sequence math problems appear in interviews at companies like Google and Amazon. The question tests mathematical reasoning, handling large ranges, and avoiding brute-force string construction.