Skip to main content
Talentd

Nth Digit - Solution & Explanation

MediumMathBinary Search12 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

 

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.

 

Constraints:

  • 1 <= n <= 231 - 1

Approach Overview

Problem Overview: You are given an integer n and must return the nth digit in the infinite sequence 123456789101112.... The sequence is formed by concatenating all positive integers. The challenge is locating which number and which digit inside that number corresponds to position n.

Approach 1: Counting Digits in Blocks (O(log n) time, O(1) space)

Numbers contribute digits in predictable blocks. All 1‑digit numbers (1–9) contribute 9 * 1 digits. Two‑digit numbers (10–99) contribute 90 * 2 digits. Three‑digit numbers contribute 900 * 3, and so on. Iterate through these blocks while subtracting their total digit contribution from n until the remaining value falls inside a specific digit-length group. Once the correct block is found, compute the exact number using division and locate the target digit using modulo indexing. This approach relies on simple arithmetic and iteration over digit ranges, making it a clean application of math reasoning.

Approach 2: Mathematical Calculation (O(log n) time, O(1) space)

This version performs the same block reasoning but formulates the calculations more directly. First determine the digit length d where the nth digit resides by subtracting blocks of size 9 * 10^(d-1) * d. Once identified, compute the exact number using start = 10^(d-1) and number = start + (n-1) / d. The desired digit index is (n-1) % d within that number. Because each step eliminates an entire digit range, the loop runs only for the number of digit lengths (at most ~10 for 32‑bit inputs). Some implementations also model the search for the correct block using binary search, but direct arithmetic is typically simpler.

Recommended for interviews: The mathematical block-counting approach is what interviewers expect. It shows that you recognize the structure of the sequence and avoid brute-force concatenation. A naive solution that actually builds the string grows too slowly and uses unnecessary memory, while the optimal math approach finds the digit in logarithmic time with constant space.

Approach 1: Counting Digits in Blocks

In this approach, we'll handle the problem by counting how many digits are in the sequence up to the point we reach our desired digit. We'll divide the sequence into blocks of digits. The first block consists of single-digit numbers, the next contains two-digit numbers, and so on.

  1. Initiate an integer variable to store the current block size, and another integer to accumulate how many digits have been counted so far.
  2. Iterate the sequence of numbers by blocks (e.g., single digits, double digits, etc.), calculating how many digits each block consumes.
  3. Once you find the block that contains the nth digit, determine the specific number and which digit within it is needed.
  4. Finally, return the identified digit.

This Python function identifies which digit corresponds to the nth number in a simulated infinite sequence of integers. By calculating the block of numbers and indexing into the correct position, you can efficiently pinpoint the desired digit.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(log n), since the number of digits in numbers grows logarithmically.
Space Complexity: O(1), constant space usage besides inputs and counters.

Try this approach in the editor →

Approach 2: Mathematical Calculation

This approach relies on recognizing the pattern and position of numbers within blocks without iterative counting. It calculates the digit using arithmetic operations and modularity. Assume a number format and work towards the digit by shifting through their positions mathematically.

  1. Determine the size of the number based on the digit length required.
  2. Calculate which number contains the needed nth digit.
  3. Directly access and return the specific digit from the number by translating n index to digit index.

In C++, string manipulation and arithmetic handles our mathematical shortcut. By computing the digit_length, identifying its respective number, and indexing the correct number within that, this solution recreates the "counting" effect using calculations.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(log n), thanks to structured digit shifts.
Space Complexity: O(1), since the processing doesn't need auxiliary memory beyond constants and simple variables.

Try this approach in the editor →

Approach 3: Mathematics

The smallest and largest integers with k digits are 10^{k-1} and 10^k-1 respectively, so the total number of digits for k-digit numbers is k times 9 times 10^{k-1}.

We use k to represent the number of digits of the current number, and cnt to represent the total number of numbers with the current number of digits. Initially, k=1, cnt=9.

Each time we subtract cnt times k from n, when n is less than or equal to cnt times k, it means that the number corresponding to n is within the range of numbers with the current number of digits. At this time, we can calculate the corresponding number.

The specific method is to first calculate which number of the current number of digits corresponds to n, and then calculate which digit of this number it is, so as to get the number on this digit.

The time complexity is O(log_{10} n).

Code

PythonJavaC++GoJavaScriptC#

Python

Java

C++

Go

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Digits in Blocks

Time Complexity: O(log n), since the number of digits in numbers grows logarithmically.
Space Complexity: O(1), constant space usage besides inputs and counters.

Mathematical Calculation

Time Complexity: O(log n), thanks to structured digit shifts.
Space Complexity: O(1), since the processing doesn't need auxiliary memory beyond constants and simple variables.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting Digits in BlocksO(log n)O(1)Best general approach. Easy to reason about by iterating through digit ranges.
Mathematical CalculationO(log n)O(1)Preferred in interviews for concise arithmetic solution.
Binary Search on Digit RangesO(log n)O(1)Useful if modeling the problem as searching for the number whose digit span contains n.

Video Solution

LeetCode 400. Nth Digit • Happy Coding • 10,661 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nth Digit easy or hard?
Nth Digit is typically rated Medium because the implementation is short but the insight about digit blocks is not immediately obvious. Once the pattern of 1-digit, 2-digit, and 3-digit ranges is recognized, the solution becomes straightforward.
How to solve Nth Digit in O(log n)?
First determine the digit length group where the nth digit lies by subtracting digit blocks such as 9×1, 90×2, 900×3. After identifying the block, compute the target number with start + (n−1)/digits and find the digit index using (n−1)%digits. Extract the digit from the resulting number.
What is the best approach for Nth Digit?
The optimal approach counts digits in number-length blocks (1-digit, 2-digit, 3-digit, etc.). Subtract each block's total digit contribution until the remaining index falls within a block, then compute the exact number and digit using division and modulo. This runs in O(log n) time with O(1) space.
What data structure is used in Nth Digit?
No special data structures are required. The solution relies on arithmetic operations and integer math to identify the correct digit block and extract the target digit.
What is the time complexity of Nth Digit?
The standard solution runs in O(log n) time and O(1) space. The loop iterates through digit lengths (1-digit, 2-digit, 3-digit...), which grows logarithmically relative to n. No large strings or arrays are created.
Nth Digit Python or Java solution approach?
Both Python and Java implementations follow the same math logic: determine the digit-length block, compute the actual number containing the digit, and index into it. Python often converts the number to a string for extraction, while Java may use arithmetic or string conversion.
Is Nth Digit asked at Google, Amazon, or Meta?
Variants of digit indexing and number sequence math problems appear in interviews at companies like Google and Amazon. The question tests mathematical reasoning, handling large ranges, and avoiding brute-force string construction.

Ready to solve this problem?

Practice Nth Digit with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer