Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.
Constraints:
- 0 ≤ n ≤ 8
Examples:
Input: 2
Output: 91
Explanation: The numbers with unique digits that are less than or equal to "10^2" are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ..., 99. There are 91 such numbers.
Solutions
Dynamic Programming
Time: O(n)Space: O(1)
This solution uses dynamic programming to calculate the count of numbers with unique digits. It starts by initializing the count to 10 (for numbers 0-9) and the unique digits to 9 (since there are 9 unique digits: 1-9). Then, for each additional digit, it multiplies the unique digits by the available numbers (which decreases by 1 each time) and adds this to the count.
public int countNumbersWithUniqueDigits(int n) {
int count = 10;
int unique = 9;
int availableNumber = 9;
if (n == 0) return 1;
if (n == 1) return count;
for (int i = 2;
i <= n;
i++) {
unique *= availableNumber;
count += unique;
availableNumber--;
}
return count;
}Follow-up:
How would you optimize this solution for larger inputs?
