Count Numbers with Unique Digits
Problem Description
Question
Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.
Example 1:
Input: n = 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99
Example 2:
Input: n = 0
Output: 1
Constraints:
0 <= n <= 8
Solve it on LeetCode
Approaches
1. Brute Force Approach
In a brute force approach, we can generate all numbers with up to n digits and count those with unique digits. However, this method will be computationally expensive due to the vast number of possibilities, making it less suitable for larger values of n.
Intuition:
- Generate all numbers with up to
ndigits. - Check each number to see if it contains unique digits.
- Count those numbers.
Code:
Complexity Analysis
- Time Complexity: O(10^n * d) where
dis the number of digits, as we have to check each number up to10^n. - Space Complexity: O(1), aside from the input and a boolean array used for verifying digit uniqueness.
2. Mathematical Combinatorics Approach
Instead of generating each number, we can use combinatorial counting to determine how many numbers have unique digits.
Intuition:
- For a given
n: - The first digit has 9 options (1 to 9), as 0 cannot be the first digit.
- The second digit has 9 options (0 to 9 except the first digit).
- The third digit has 8 options, and so on.
- Use combinatorial multiplication to compute the count of numbers with unique digits.
Code:
Complexity Analysis
- Time Complexity: O(n), as each digit added requires constant time calculations.
- Space Complexity: O(1), as we are not using any additional space that grows with
n.