How do you solve Nth Digit on LeetCode?

Nth Digit (LeetCode #400) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Understanding how to calculate ranges of numbers based on digit length is crucial.

What is the brute force solution for Nth Digit?

The brute force approach for Nth Digit is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating the sequence of numbers one by one until we reach the nth digit. This is straightforward but inefficient for large n. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Nth Digit?

Nth Digit uses the following concepts: Math, Binary Search. The recommended patterns to study are: Mathematical reasoning, Binary Search.

What are the interview tips for Nth Digit?

Always clarify the constraints and edge cases before diving into coding. Explain your thought process as you work through the problem. Practice similar problems to get comfortable with mathematical reasoning.

What are common mistakes when solving Nth Digit?

Failing to account for the transition between digit lengths. Not realizing that the nth digit can be in a multi-digit number.

#400

Nth Digit

Medium

MathBinary SearchMathematical reasoningBinary Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

Instead of generating all numbers, we can mathematically determine which number contains the nth digit by calculating ranges of digits based on the number of digits in the numbers.

⚙️

Algorithm

3 steps

1Step 1: Determine how many digits the nth digit falls into by calculating ranges of numbers with 1 digit, 2 digits, etc.
2Step 2: Find the specific number that contains the nth digit by subtracting the total digits accounted for from n.
3Step 3: Calculate the actual number and the specific digit within that number.

solution.py13 lines

1def findNthDigit(n):
2    digit = 1
3    count = 9
4    start = 1
5    while n > digit * count:
6        n -= digit * count
7        digit += 1
8        count *= 10
9        start *= 10
10    start += (n - 1) // digit
11    return int(str(start)[(n - 1) % digit])
12
13print(findNthDigit(11))

ℹ

Complexity note: The complexity is O(log n) because we are effectively dividing the problem size by 10 each time we increase the digit count.

1Understanding how to calculate ranges of numbers based on digit length is crucial.
2Recognizing that we can avoid generating all numbers saves time and resources.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.