357 Count Numbers with Unique Digits
Given anon-negativeinteger n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding
[11,22,33,44,55,66,77,88,99]
)The Idea:
- If
n == 0
, we can only choseor just one thing. - When
n == 1
, we can choosethings, that isthings - When
n == 2
, we can choose a permutation of 2 things, that is...
01, 02, 03 ... 09
12, 13, 14 ... 19
21, 23, 24 ... 29
- Which equates to
P(10, 2)
things. But we have some redundancy, that is those 0's in the beginning, which are effectively the same thing as0,1,2,3,4,...9
. To get rid of these, we subtractP(9,1)
to get rid of just those 9 elements. - When
n == 4
, we can likewise choseP(10,4)
things. But what is the redundancy here. Lets think about it.
012, 013, .. 019
021, 023, .. 029
031, 032, .. 039
...
091, 092, .. 098
- We find 9 elements per row, for 8 rows. This follows
9*8
, orP(9,2)
- It then follows that the number of numbers of unique Digits are
int permutation(int num, int choose)
{
int cur = 1;
int go_to = num - choose;
for (int i = num; i > go_to; i--)
cur *= i;
return cur == 1 ? 0 : cur;
}
int countNumbersWithUniqueDigits(int n)
{
if (n == 0) return 1;
int prev_perm = 0;
for (int i = 1; i <= n; i++) {
prev_perm += permutation(10, i) - permutation(9, i - 1);
}
return prev_perm;
}
Last modified 4yr ago