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 - 1Problem 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.
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.
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.
Python
JavaScript
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.
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.
nth digit.n index to digit index.In C++, string manipulation and arithmetic handles our mathematical shortcut. By computing the digit_length, identifying its respective number, and indexing the correct number within that, this solution recreates the "counting" effect using calculations.
Time Complexity: O(log n), thanks to structured digit shifts.
Space Complexity: O(1), since the processing doesn't need auxiliary memory beyond constants and simple variables.
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).
| 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), thanks to structured digit shifts. |
| Mathematics | — |
| 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. |
LeetCode 400. Nth Digit • Happy Coding • 10,321 views views
Watch 9 more video solutions →Practice Nth Digit with our built-in code editor and test cases.
Practice on FleetCode