265. Distinct-Digit Counts
A locker company issues numeric codes with no leading padding, so the code 7 is just "7" and the code 4051 has four digits. A code is called scattered if no digit value appears twice in it; for instance 4051 is scattered but 4041 is not.
Given n, return how many integers x with 0 <= x < 10^n are scattered. Zero itself counts (it is the single digit "0"), so for n = 0 the range is just {0} and the answer is 1. The answer always fits a 32-bit integer. Counting with permutation formulas runs in O(n) time and O(1) space; testing every number would take 10^n steps.
Example 1
- Input:
- n = 4
- Output:
- 5275
- Explanation:
There are 1 + 9 + 81 + 648 + 4536 = 5275 scattered integers with at most four digits.
Example 2
- Input:
- n = 0
- Output:
- 1
- Explanation:
The range is only {0}, which is scattered.
Constraints
0 ≤ n ≤ 10
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)