Nth Digit: Math Pattern Recognition

May 18, 20265 min read

leetcodeproblemmediummath

LeetCode Nth Digit (Problem 400) asks you to find the nth digit in the infinite sequence formed by concatenating all positive integers: 1, 2, 3, ... , 9, 10, 11, 12, ... . The sequence of individual digits is 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 ..., and you need to return the digit at position n.

This is a pure math problem. No data structures, no traversal, just careful counting across number ranges.

The problem

Given an integer n, return the nth digit in the sequence formed by concatenating all positive integers.

Input: n = 11
Output: 0
Explanation: The sequence is 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 .... The 11th digit is 0, which is part of the number 10.
Input: n = 3
Output: 3
Explanation: The 3rd digit in the sequence is simply 3.

Positive integers written out sequentially as individual digits. Position 11 lands on the "0" in the number 10.

Why range counting works

The key insight is that numbers with the same digit count form predictable ranges, and each range contributes a fixed total number of digits.

1-digit numbers (1 through 9): There are 9 numbers, each contributing 1 digit. Total: 9 * 1 = 9 digits.
2-digit numbers (10 through 99): There are 90 numbers, each contributing 2 digits. Total: 90 * 2 = 180 digits.
3-digit numbers (100 through 999): There are 900 numbers, each contributing 3 digits. Total: 900 * 3 = 2700 digits.

The pattern generalizes: for d-digit numbers, the count of numbers is 9 * 10^(d-1), the starting number is 10^(d-1), and the total digits contributed is 9 * 10^(d-1) * d.

To find the nth digit, you subtract each range's total from n until you land in the correct range. Then you compute exactly which number and which digit within that number.

The digit count formula for each range is count = 9 * start * digits, where start is 10^(d-1) and digits is d. This gives you 9, 180, 2700, 36000, ... for 1-digit, 2-digit, 3-digit, 4-digit ranges. Memorize this pattern and the rest of the solution follows naturally.

Step-by-step walkthrough

Let's trace through the algorithm with n = 11.

Step 1: Subtract 1-digit range (1-9). Count = 9 * 1 * 1 = 9 digits.

1-digit numbers (1-9) contribute 9 digits. After subtracting, n = 2 tells us we need the 2nd digit in the 2-digit range.

Step 2: Locate the exact number and digit within the 2-digit range.

With n = 2 remaining in the 2-digit range (starting at 10), we compute: number = 10 + floor((2-1)/2) = 10. Digit index = (2-1) % 2 = 1. The digit at index 1 in "10" is "0".

The two-step process is always the same: subtract ranges to find which digit-length group you are in, then do division and modulo to pinpoint the exact number and position.

Drill math pattern problems with SRS

The code

def findNthDigit(n):
    digits = 1
    start = 1
    count = 9

    while n > count:
        n -= count
        digits += 1
        start *= 10
        count = 9 * start * digits

    num = start + (n - 1) // digits
    idx = (n - 1) % digits
    return int(str(num)[idx])

The while loop subtracts each range's contribution until n fits within the current range. At that point, digits tells you how many digits per number, and start is the first number in that range (1, 10, 100, ...).

The target number is start + (n - 1) // digits. You use n - 1 because the range is 1-indexed: when n = 1, you want the first digit of start itself. The digit index within that number is (n - 1) % digits. Finally, convert the number to a string and extract the character at that index.

Watch for off-by-one errors. The subtraction n - 1 before dividing is essential because positions within the range are 1-based but string indexing is 0-based. Getting this wrong by even one position will produce the wrong digit. Also, for very large n, make sure your language handles large integer arithmetic correctly (Python does this natively, but in Java or C++ you may need long).

Complexity analysis

Approach	Time	Space
Range counting	O(log n)	O(1)

The while loop runs at most O(log n) times since each iteration covers an exponentially larger range of numbers. The final computation is constant time: one division, one modulo, one string conversion of a bounded-length number.

Practice this problem with spaced repetition

The building blocks

Digit range counting

The core technique is partitioning the infinite sequence into ranges based on digit length. You will see this same idea in other digit-counting problems.

The formula 9 * 10^(d-1) * d gives the total digits contributed by all d-digit numbers. Once you know which range n falls into, simple integer division and modulo locate the exact number and position. This pattern recurs in Number of Digit One, where you count how many times a specific digit appears across ranges.

The range-counting technique is reusable whenever a problem asks about the "position" or "count" of something within a number sequence. If you see a problem involving digits of consecutive integers, think about grouping by digit length first.

Edge cases

n = 1: The first digit in the sequence is 1. The loop body never executes, num = 1, idx = 0, and str(1)[0] = "1".
n = 9: The last single-digit position. num = 9, idx = 0, result is 9.
n = 10: The first digit of the 2-digit range. After subtracting 9 (the 1-digit range), n = 1. num = 10 + 0 = 10, idx = 0, so the answer is 1 (the first digit of 10).
n = 11: The second digit of 10, which is 0. This is the main example we traced.
Large n (e.g., n = 1,000,000,000): The algorithm still runs in O(log n) since it only loops through roughly 9-10 digit-length ranges before finding the target. No performance issue even for the maximum constraint.

From understanding to recall

Reading through this solution takes a couple of minutes. But can you reproduce the formula 9 * start * digits and the offset calculation start + (n - 1) // digits from memory in an interview? Most people cannot, at least not reliably.

Spaced repetition fixes that. CodeBricks breaks this problem into its building blocks: the digit-range counting loop and the number/digit offset computation. You practice each piece at increasing intervals until writing it becomes automatic. The next time you see a digit-position problem, you will not be deriving the formula from scratch. You will just write it.

Factorial Trailing Zeroes - counting patterns in number ranges
Number of Digit One - digit-level analysis across number ranges
Add Digits - math tricks with digit manipulation

That is the entire solution for Nth Digit. The problem rewards careful arithmetic more than clever algorithms. Get the range subtraction right, get the offset indexing right, and the answer falls out.

Start drilling math patterns today