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 Sam K., 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

More Math practice problems

See all Math problems →