Count Numbers with Unique Digits
Medium · Backtracking · Explanation and code example
Count Choices by Digit Length
How it works
Count zero and all one-digit values first. For a longer number, its first digit has nine choices and each following digit has one fewer unused choice. Sum the counts for each valid length; there are no unique-digit numbers longer than ten digits.
Steps
- Handle n = 0 as the single value zero.
- Start with ten one-digit values.
- Multiply available choices for each new digit length and add the count.
Complexity
- Time: O(min(n, 10)).
- Space: O(1).
Things to watch for
- The first digit cannot be zero.
- Zero still counts as a value.
- Stop once all ten digits have been used.
Python code example
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n == 0:
return 1
ans = 10
uniqueDigits = 9
availableNum = 9
while n > 1 and availableNum > 0:
uniqueDigits *= availableNum
ans += uniqueDigits
n -= 1
availableNum -= 1
return ans
C++ code example
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (n == 0)
return 1;
int ans = 10;
int uniqueDigits = 9;
for (int availableNum = 9; n > 1 && availableNum > 0; --n, --availableNum) {
uniqueDigits *= availableNum;
ans += uniqueDigits;
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.