Python 0400.py
class Solution:
def findNthDigit(self, n: int) -> int:
# the number has a special name, it's called the Champernowne constant
# (if joining all digits and preceded them with "0.")
# I knew it from my Project Euler 40 solution:
# https://euler.stephan-brumme.com/40/
# the code below was 1:1 translated from C++ to Python
# except that variable "pos" is named "n"
# assume pos has one digit
digits = 1
# then there are 9 other numbers
range = 9
# the smallest of them is 1
first = 1
# there are 9 numbers with 1 digits
# there are 90 numbers with 2 digits
# there are 900 numbers with 3 digits
# there are 9000 numbers with 4 digits
# ...
# let's figure out the number of digits
# skip numbers with too few digits
skip = 0
while (skip + digits*range < n):
skip += digits * range
# digits = 2 => range = 90 and
# digits = 3 => range = 900
# digits = 4 => range = 9000, etc.
digits += 1
range *= 10
first *= 10
# now that we know the number of digits
# adjust "first" and "skip" such that the left-most/highest digit of pos and skip are identical
# then continue with the next digit
while range > 9:
# could be replace by some modular arithmetic, but I'm too lazy for tough thinking ;-)
while skip + digits*range < n:
skip += digits*range
first += range
# next lower digit
range //= 10 # note: was / in C++, needs to be // in Python (int division)
# right-most digit (basically same inner loop as above when range == 1)
while (skip + digits < n):
first += 1
skip += digits
# skip all "skippable" digits
n -= skip
# strings are zero-based whereas input is one-based
s = str(first)
return int(s[n - 1])
Difficulty
and has an acceptance rate of about 38% (300k+ submissions).
Typical patterns to solve this problem:
- Binary Search
- Math
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The routine computes the digit that appears at the n-th position in the infinite decimal formed by concatenating the positive integers (the Champernowne constant). It works by first determining the length of the block of numbers that contains the target digit, then narrowing down to the exact integer, and finally extracting the required character from its string representation. The algorithm proceeds in three distinct phases: establishing the digit-group size, iteratively advancing through groups of equal length, and performing a final offset calculation.
Initialization
The method begins by setting up variables that describe the current digit group. digits holds the number of digits of the numbers in the current group, range is the count of numbers in that group, and first is the smallest number in the group.
digits = 1
range = 9
first = 1
At this point the algorithm assumes the target lies somewhere after the initial digit group of one-digit numbers.
Skipping groups with insufficient digits
A loop accumulates the total number of digits that can be skipped (skip) while the cumulative count remains less than the target position n. In each iteration the group size expands by a factor of ten, reflecting the transition from one-digit numbers to two-digit numbers, and so on.
skip = 0
while (skip + digits * range < n):
skip += digits * range
digits += 1
range *= 10
first *= 10
When the loop exits, digits and range describe the block that actually contains the n-th digit, and first points to the first number of that block.
Refining within the same digit length
The next phase narrows the search inside the identified block. The outer loop reduces range until it reaches the single-digit granularity. Inside, a nested loop continues to skip whole numbers as long as doing so does not overshoot the target.
while range > 9:
while skip + digits * range < n:
skip += digits * range
first += range
range //= 10
The integer division (//) mirrors the original C++ division and guarantees that range stays integral. By repeatedly subtracting whole-number contributions, the algorithm aligns first with the exact integer that holds the desired digit.
Handling the final digit positions
When range has been reduced to one, the algorithm deals with the remaining individual digits. It increments first one by one, adding the digit count of each number to skip until the next increment would exceed n.
while (skip + digits < n):
first += 1
skip += digits
At this stage first is the exact integer that contains the target digit, and skip is the count of digits that precede it.
Extracting the digit
The remaining offset is computed by subtracting the already skipped digits from n. Because Python strings are zero-based, the code accesses the character at position n-1 after converting first to a string.
n -= skip
s = str(first)
return int(s[n - 1])
The conversion to a string occurs only once, minimizing overhead.
Edge-case handling
When n equals 1, the initial while condition fails immediately, leaving digits, range, and first at their initial values. The subsequent loops also bypass any skipping, and the final extraction returns the first character of "1", correctly yielding 1.
If n lands exactly at the boundary between two digit groups (for example, the last digit of the two-digit block), the outer skipping loop stops just before the boundary, and the inner refinement loop advances first to the first number of the next group without overshooting, ensuring the correct digit is selected.
For very large n, the algorithm scales by repeatedly multiplying range and first by ten, which efficiently jumps across massive spans of numbers without iterating through each individual integer. The final loops then perform only a handful of arithmetic steps before the string conversion, keeping the runtime bounded by the number of digit groups rather than the magnitude of n.
Performance optimizations
The primary optimization is the use of arithmetic progression formulas to skip entire blocks of numbers in constant time per digit group. By accumulating skip as digits * range, the code avoids a linear scan of each integer. The reduction of range by integer division eliminates the need for modular arithmetic, simplifying the logic while preserving correctness. Additionally, the algorithm postpones any string manipulation until the very end, ensuring that the expensive conversion is performed only once for the final integer. This combination of block skipping, integer arithmetic, and delayed string conversion yields a solution that runs quickly even for inputs deep into the Champernowne sequence.
ELI5 - Simplified Explanation
Imagine there is a never-ending train of numbers chugging along a track. The first carriage has a 1, the next has a 2, then a 3, and this keeps going all the way up to 9. Once the train gets to 10, the numbers start having two digits, then three, and it grows bigger and bigger forever. The goal is to find a specific digit at a secret spot way down the line.
To find this, the code acts like a very smart detective. First, it counts how many tiny numbers are in the train. It knows that there are nine numbers with one digit, ninety numbers with two digits, nine hundred with three digits, and so on. By looking at how big the secret spot is, it can skip over huge sections of the train to get closer to the right area.
Once it figures out which group of numbers the spot is hiding in, it narrows things down. It checks the groups digit by digit, skipping through them until it finds the exact number holding the hidden spot. After it finally lands on the right number, it turns that number into a line of text so it can look at each individual digit one by one. It picks the one at the secret spot, and that is the answer.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||||
| WalkCCC | C++ | Java | Python | ||||||||
| leetcode.ca | C++ | Java | JS | Python | Go | C# | |||||
| LeetcodeHelp | C++ | Java | Python | ||||||||
| Progiez | C++ | Java | Python | ||||||||
| github | black-shadows | C++ | |||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| qiyuangong | Java | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, Python | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| lzl124631x | C++ | ||||||||||
| qiyuangong | Java | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 1013: Partition Array Into Three Parts With Equal Sum
- problem 1668: Maximum Repeating Substring
- problem 1736: Latest Time by Replacing Hidden Digits
- problem 1784: Check if Binary String Has at Most One Segment of Ones
- problem 2099: Find Subsequence of Length K With the Largest Sum
- problem 2383: Minimum Hours of Training to Win a Competition
- problem 2511: Maximum Enemy Forts That Can Be Captured
- problem 2739: Total Distance Traveled
- problem 331: Verify Preorder Serialization of a Binary Tree
- problem 447: Number of Boomerangs
- problem 1476: Subrectangle Queries
- problem 1828: Queries on Number of Points Inside a Circle
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality