Nth Digit

Medium
437.

Nth Digit

Nth Digit is a medium coding problem on math and binary search, asked in Amazon, Google and Bloomberg interviews.

Consider the infinite sequence formed by writing the positive integers one after another: 123456789101112…

Given an integer n, return the n-th digit of that sequence (1-indexed).

Example 1

Input
n = 3
Output
3

Example 2

Input
n = 11
Output
0
Explanation
The 11th digit falls inside 10.

Example 3

Input
n = 1000000000
Output
1

Constraints

  • 1 <= n <= 2147483647
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var findNthDigit = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Nth Digit — Solution in Python, Java & C++

Nth Digit solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Nth Digit is a medium coding problem on math and binary search, asked in Amazon, Google and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Math, Binary Search
  • Asked at: Amazon, Google, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Consider the infinite sequence formed by writing the positive integers one after another: 123456789101112…

Given an integer n, return the n-th digit of that sequence (1-indexed).

Example 1

Input: n = 3
Output: 3

Example 2

Input: n = 11
Output: 0
Explanation: The 11th digit falls inside 10.

Example 3

Input: n = 1000000000
Output: 1

Constraints

  • 1 <= n <= 2147483647

Hints for Nth Digit

  1. Hint 1

    There are 9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, and so on.

  2. Hint 2

    Subtract those blocks from n until it lands inside the block of d-digit numbers.

  3. Hint 3

    Then integer division pinpoints the number and the remainder pinpoints the digit inside it — use 64-bit arithmetic so the block sizes do not overflow.

How to solve Nth Digit

Skip whole blocks — 9 one-digit numbers, 90 two-digit, 900 three-digit — until n lands in the block of d-digit numbers, then locate the number and the digit within it.

Approach

  1. While n > digits · count: subtract, then digits++, count *= 10, start *= 10.
  2. value = start + (n - 1) // digits; return digit (n - 1) % digits of value.

Why it works

Digit positions are consecutive across the numbers of a block, so integer division by the block's digit width maps the offset to a number and the remainder to a digit.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Use 64-bit arithmetic for digits · count.

Reference solution

Python

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

Java

public static int findNthDigit(int n) {
    long remaining = n;
    long digits = 1;
    long count = 9;
    long start = 1;
    while (remaining > digits * count) {
        remaining -= digits * count;
        digits++;
        count *= 10;
        start *= 10;
    }
    long value = start + (remaining - 1) / digits;
    String text = String.valueOf(value);
    return text.charAt((int) ((remaining - 1) % digits)) - '0';
}

C++

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

JavaScript

var findNthDigit = function(n) {
    let remaining = n;
    let digits = 1;
    let count = 9;
    let start = 1;
    while (remaining > digits * count) {
        remaining -= digits * count;
        digits++;
        count *= 10;
        start *= 10;
    }
    const value = start + Math.floor((remaining - 1) / digits);
    const text = String(value);
    return Number(text.charAt((remaining - 1) % digits));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search