Watch 10 video solutions for Nth Digit, a medium level problem involving Math, Binary Search. This walkthrough by Happy Coding has 10,321 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |