Python 0902.py
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
s = str(n)
# single digit
if n < 10:
return sum([ 1 if d <= s else 0 for d in digits ])
# numbers with less digits than n can be generated without restrictions
result = 0
for i in range(1, len(s)):
result += len(digits) ** i
# for each digit d smaller than the first digit of n
# we can generate all numbers with len(n) - 1 digits
for i in range(len(s)):
remaining = (len(s) - 1) - i
for d in digits:
if d < s[i]: # but not d == s[i] !!!
result += len(digits) ** remaining
if s[i] not in digits:
# no more restrictions
break
if remaining == 0: # and s[i] in digits
result += 1 # the only case where d == s[i] is counted
return result
Difficulty
and has an acceptance rate of about 46% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Binary Search
- Dynamic Programming
- Math
- String
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 atMostNGivenDigitSet method computes how many positive integers not larger than n can be built using only the characters supplied in digits. The algorithm works by separating the problem into three conceptual parts: a trivial single-digit case, counting all numbers that have fewer digits than n, and a digit-by-digit walk through the representation of n to handle numbers that share the same length.
Key Steps
Converting the target number to a string
The first operation transforms the integer n into its decimal string representation. This enables direct character comparison with the elements of digits.
s = str(n)
Immediate handling of single-digit targets
When n is less than ten, every admissible number is a single digit. The code iterates over digits and counts those whose character value does not exceed the single character of s.
if n < 10:
return sum([ 1 if d <= s else 0 for d in digits ])
Counting numbers with fewer digits than n
All numbers whose length is strictly smaller than the length of s can be formed without any restriction from n. For each possible length i (starting at one), the total count is the size of digits raised to the power i. The loop accumulates these contributions.
result = 0
for i in range(1, len(s)):
result += len(digits) ** i
Digit-by-digit processing of numbers with the same length as n
The core of the algorithm iterates over each position i of s. For the current position it computes how many numbers can be formed by choosing a digit smaller than the corresponding digit of n while freely filling the remaining positions.
for i in range(len(s)):
remaining = (len(s) - 1) - i
for d in digits:
if d < s[i]: # strictly smaller digit
result += len(digits) ** remaining
if s[i] not in digits:
break # further positions cannot match n
if remaining == 0: # last digit matches and is allowed
result += 1
The inner loop adds len(digits) ** remaining for each digit d that is strictly less than the current character of s. If the current character of s does not belong to digits, the outer loop terminates early because any longer prefix would already exceed the allowed set. When the loop reaches the final position and the digit matches, the exact number n itself is counted.
Edge Cases Handled
When n is a single digit, the early return bypasses all later logic, ensuring that the function does not mistakenly apply the multi-digit counting scheme. The presence of the digit '0' in digits does not cause incorrect counts because the algorithm never generates numbers with a leading zero: the first position is always filled by any digit from digits, but the power-based counting implicitly treats each position independently, and the early break prevents continuation when a required digit is missing. If digits is unsorted, the comparisons d < s[i] and s[i] not in digits still work correctly because they rely on character ordering and membership testing, both of which are independent of list order. The loop termination condition if s[i] not in digits: break guarantees that once a prefix cannot be matched, no further numbers of the same length are considered, correctly handling cases where n contains a digit absent from the allowed set.
Performance Optimizations
The implementation avoids constructing intermediate lists of candidate numbers; instead it uses arithmetic on the size of digits to compute counts directly. Raising len(digits) to a power is performed with the built-in exponentiation operator, which is highly optimized in CPython. The early break when a digit of n is not present in digits prevents unnecessary iteration over the remaining positions, reducing the number of exponentiations in many inputs. By handling the single-digit case up front, the function skips the more expensive loops for trivial inputs, delivering constant-time performance for that branch. Overall, the algorithm runs in time proportional to the number of digits in n, with only a small constant factor contributed by the inner loop over digits.
ELI5 - Simplified Explanation
Imagine you have a big box of numbered blocks. Each block has a special digit written on it, like a little stamp. You want to build some secret codes, but there is a rule. You cannot make a code that represents a number bigger than the number n written on a piece of paper.
First, think about codes that are shorter than the number n. If n has three digits, a code with only one or two digits will always be smaller. You just count how many ways you can pick any combination of your blocks for those shorter lengths.
Next, you look at codes that have the same number of digits as n. You start from the very first spot on the left. You try putting each of your blocks there. If the digit on your block is smaller than the digit in that same spot on n, it means any combination of blocks you pick for the rest of the spots will be a winner because the whole number is already smaller than n.
If one of your blocks matches the digit in that spot exactly, you move to the next spot to keep checking. You keep doing this for every position. If you ever find that none of your blocks match the digit in n, you stop because you cannot make any more codes that look like n. If you manage to make it all the way to the end and find that you can match every single digit in n, you count that one full match as a secret code too.
Code Quality
Complexity Analysis
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++ | Python | Java | TS | ||||
| WalkCCC | C++ | Python | Java | ||||||
| leetcode.ca | C++ | Python | Java | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | ||||||
| Progiez | C++ | Python | Java | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fpdjsns | C++ | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fpdjsns | C++ | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ |
Videos
Similar Problems
- problem 483: Smallest Good Base
Solved On The Same Day
- problem 1005: Maximize Sum Of Array After K Negations
- problem 935: Knight Dialer
- problem 1029: Two City Scheduling
- problem 1769: Minimum Number of Operations to Move All Balls to Each Box
- problem 2080: Range Frequency Queries
- problem 793: Preimage Size of Factorial Zeroes Function
- problem 878: Nth Magical Number
- problem 1751: Maximum Number of Events That Can Be Attended II
- problem 1793: Maximum Score of a Good Subarray
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