Count Positive Numbers with No Repeated Decimal Digit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Return the number of positive integers in the inclusive interval `[1, n]` whose decimal digits are all distinct. Use each integer's usual decimal representation, without leading zeroes.
```cpp
class Solution {
public:
int countSpecialNumbers(int n);
};
```
### Examples
**Example 1:**
```text
Input: n = 12
Output: 11
Explanation: Only 11 repeats a digit among the integers from 1 through 12, leaving eleven special integers.
```
**Example 2:**
```text
Input: n = 100
Output: 90
Explanation: There are 9 one-digit and 9*9 = 81 two-digit choices. The number 100 repeats zero, so the total is 90.
```
### Constraints
- `1 <= n <= 2000000000`.
### Clarifying Questions
- Is zero included? No, the interval starts at 1.
- Can a qualifying number contain the digit zero? Yes, as long as no digit repeats.
- Do leading zeroes count as digits? They are not part of the usual representation.
- Is the upper bound included? Yes.
```hint Check the boundary
Compare 10, 100 and 101 under the distinct-digit rule.
```
Overview: Count positive integers up to an inclusive bound whose usual decimal representations have no repeated digits.