📘 Problem Statement
Given an integer n, return the count of all numbers with unique digits where the number length is less than or equal to n.
0 <= n <= 8- For example, for
n = 2, count all numbers with 0 to 2 digits and no repeated digits.
🧠 Core Concept
We're essentially counting how many numbers of length 1 to n can be formed using non-repeating digits (0–9).
This is a combinatorics problem where we:
- Use permutation logic.
- Compute:
- 1-digit unique numbers
- 2-digit unique numbers
- ...
- Up to
n digits unique numbers
✍️ Formula Breakdown
- For 1-digit: 10 (0–9)
- For 2-digit: 9 × 9 (first digit ≠ 0, second ≠ first)
- For 3-digit: 9 × 9 × 8
- For 4-digit: 9 × 9 × 8 × 7
- …and so on.
General formula:
python
count = 9 × (9) × (8) × (7) × ... up to (10 - i + 1)
🐍 Python Implementation
python
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n == 0:
return 1
total = 10 # All 1-digit numbers
unique_digits = 9
available = 9
for i in range(2, n + 1):
unique_digits *= available
total += unique_digits
available -= 1
return total
🔍 Step-by-Step Explanation
Let's say n = 3
We compute:
- 1-digit: 10 numbers (0–9)
- 2-digit: 9 × 9 = 81 (1st digit: 1–9, 2nd digit: 0–9 except the 1st digit)
- 3-digit: 9 × 9 × 8 = 648
✅ Total = 10 + 81 + 648 = 739
⏱️ Time & Space Complexity
OperationComplexityTimeO(n)SpaceO(1)
🧪 Edge Case
- If
n = 0, only number 0 is valid ⇒ return 1.
🧵 Final Thoughts
This is a classic permutations-based counting problem, useful for:
- Practicing combinatorics
- Understanding permutations without repetitions
- Learning how to translate math formulas into code