This is a maths question and not a dynamic programming question and is not really a good interview question.
Let’s look at the numbers having unique digits:
- No. of digits = 1: the numbers can be from 1..9 so answer is 9
- No. of digits = 2: For each number b/w 1 and 9, we can append another digit not equal to that number. For example, we can append 0,2,3,4,5,6,7,8,9 to 1 to make numbers [10, 12, 13, 14, 15, 16, 17, 18, 19]. Notice that we did not take 1 itself as we need unique digits. So total such numbers = 9*9.
- No. of digits = 3: For each number b/w 1 and 9, we can append two unique digits to make a three digit number. Let’s take the example of 1 again. The first number to be appended should not be = 1 so available choices = 9 (0,2,3,4,5,6,7,8,9). The next number should not be equal to 1 and also not equal to the previous number selected so number of choices = 8. So total number of ways = 998
- No. of digits = 4: 998*7 & so on till no. of digits = 10
Coming back to the actual question:
- For n=0, 10^0 = 1 so only valid answer is 1
- For
0 < n <= 10, number of digits vary from 1 to 10 so answer would be sum of number of ways for each number of digit < n.
We can either calculate the answer each time or just preprocess it once in a static array for each test case. The below implementation uses a static vector which is processed only the first time:
static vector<int> res;
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (res.size()==0) {
res.push_back(1);
res.push_back(9);
for (int i=0, j=9; i<9; i++, j--) {
res.push_back(res[i+1]*j);
}
for (int i=1; i<res.size(); i++)
res[i]+=res[i-1];
}
if (n>10)
return res[10];
return res[n];
}
};
Time complexity: O(1)