Skip to main content

400. Nth Digit

medium

Find the nth digit in the infinite sequence 123456789101112... A pure indexing problem: identify the digit-length block, then the specific number, then the digit within it.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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, ...].

Constraints

  • 1 <= n <= 2^31 - 1

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count digits per 'length' block. 1-digit numbers contribute 9 * 1 = 9 digits. 2-digit numbers contribute 90 * 2 = 180. 3-digit contribute 900 * 3 = 2700. In general k-digit contribute 9 * 10^(k-1) * k digits.

Hint 2

Subtract block sizes from n until you find the block where the answer lives. Track 'digit length k' and the starting number of that block.

Hint 3

Inside the block, the answer is in the ((n - 1) / k)-th number after the block's first. Use integer division.

Hint 4

Within that number, the answer is the ((n - 1) % k)-th digit (0-indexed).

Solution approach

Reveal approach

Subtract blocks. Let digit_len = 1, start = 1, count = 9. While n > digit_len * count: n -= digit_len * count; digit_len += 1; start *= 10; count *= 10. After the loop you know the answer lies in the digit_len-block whose first number is start. Find the target number: target = start + (n - 1) / digit_len. Find the digit within target: digit_index = (n - 1) % digit_len. Convert target to string and return its digit_index-th character as an integer. O(log n) iterations of the block-skipping loop, O(log n) work per iteration on the integer-to-string conversion. O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • math
  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Nth Digit and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →