Nth Digit

medium math binary search

Problem

Consider the infinite string formed by concatenating positive integers: "123456789101112…". Return the n-th digit (1-indexed).

Inputn = 11

Output0

After skipping 9 single-digit numbers we have 2 digits left in the 2-digit band → land in "10" at offset 1 → '0'.

def find_nth_digit(n):
    digits, count, start = 1, 9, 1
    while n > digits * count:
        n -= digits * count
        digits += 1
        count *= 10
        start *= 10
    num = start + (n - 1) // digits
    offset = (n - 1) % digits
    return int(str(num)[offset])

function findNthDigit(n) {
  let digits = 1, count = 9, start = 1;
  while (n > digits * count) {
    n -= digits * count;
    digits++;
    count *= 10;
    start *= 10;
  }
  const num = start + Math.floor((n - 1) / digits);
  const offset = (n - 1) % digits;
  return parseInt(String(num)[offset], 10);
}

class Solution {
    public int findNthDigit(int n) {
        long digits = 1, count = 9, start = 1;
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
        long num = start + (n - 1) / digits;
        int offset = (int)((n - 1) % digits);
        return Long.toString(num).charAt(offset) - '0';
    }
}

int findNthDigit(int n) {
    long long digits = 1, count = 9, start = 1;
    while (n > digits * count) {
        n -= digits * count;
        digits++;
        count *= 10;
        start *= 10;
    }
    long long num = start + (n - 1) / digits;
    int offset = (n - 1) % digits;
    return to_string(num)[offset] - '0';
}

Explanation

Instead of building the giant string "123456789101112…" one character at a time, we jump past whole bands of numbers that share the same digit-length. That makes it fast even for huge n.

The numbers group into bands: there are 9 one-digit numbers (using 9 digits), 90 two-digit numbers (180 digits), 900 three-digit numbers (2700 digits), and so on. We track digits (length of numbers in the band), count (how many numbers in the band), and start (the first number of the band). While n is bigger than the band's total digits * count, we subtract that and advance to the next band.

Once n fits inside the current band, the number we land on is num = start + (n - 1) // digits, and the exact character is at offset = (n - 1) % digits inside that number's string.

Example: n = 11. The one-digit band has only 9 digits, so subtract 9, leaving n = 2 in the two-digit band that starts at 10. Then num = 10 + (2-1)//2 = 10 and offset = (2-1) % 2 = 1, so we take "10"[1] = '0'.

Because each loop step skips an entire band, the number of steps grows only with the number of digits in n, giving logarithmic time.

Time: O(log n) Space: O(1)