Count Numbers with unique digits
Given a non-negative integer n, count all numbers with unique digits, x, 0<=x<10^n.
Input & output:
n=2
Total numbers that can be formed is 91
Explanation with example
For n =2.
Total numbers = 0 to 102 (excluding)
except 11, 22, 33, 44, 55, 66, 77, 88, 99 which has repeated digits.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Then for the first digit (from left), we have 9 choices (excluding 0) [1 to 9]
And for second digit we have 9 choices (0 to 10 except the previous digit)
So basically, the number is:
ij where i=[1,9] and j=[0,9]and i≠j
So, total number possible are 9*9=81
Then for first digit (from left), we have 9 choices (excluding 0) [1 to 9]
And for second digit we have 9 choices (0 to 10 except the previous digit)
And for third digit we have 8 choices (0 to 10 except the previous two digits)
So basically, the number is:
ijk where i=[1,9] and j,k=[0,9]and i≠j & j≠k,i
So, total number possible are 9*9*8=648
So, if number of digits is i, then the ith digit will have (10-i+1) choices
So, we can formulate
Now this above recursion can be implemented using dynamic programming.
C++ Implementation:
Output