# Java, O(1), with explanation

• This is a digit combination problem. Can be solved in at most 10 loops.

When n == 0, return 1. I got this answer from the test case.

When n == 1, _ can put 10 digit in the only position. [0, ... , 10]. Answer is 10.

When n == 2, _ _ first digit has 9 choices [1, ..., 9], second one has 9 choices excluding the already chosen one. So totally 9 * 9 = 81. answer should be 10 + 81 = 91

When n == 3, _ _ _ total choice is 9 * 9 * 8 = 684. answer is 10 + 81 + 648 = 739

When n == 4, _ _ _ _ total choice is 9 * 9 * 8 * 7.

...

When n == 10, _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

When n == 11, _ _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 = 0

``````public static int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
int ans = 10, base = 9;
for (int i = 2; i <= n && i <= 10; i++) {
base = base * (9 - i + 2);
ans += base;
}
return ans;
}``````

• Hi, this may be late but I am wondering when n=2 why is it 9* 9 and not 9*8? Because you said that you exclude the already chosen one so shouldn't the number of digits you have to work with be 1 less? I am just trying to understand for the sake of my understanding, thank you very much!

• 0 can't be put in first first position, but 0 can be put in other positions. It's because of 0.

• The explanation is quit clear. The only thing is the for loop conditions is not that straight forward. I made a little bit change based on your solution. See detail below:

``````public int countNumbersWithUniqueDigits(int n) {
if(n==0) return 1;
if(n==1) return 10;

int ans = 10, base = 9;
//i: next multi-factor, j: control loop count
for(int i=9, j=n-1; i>0 && j>0; i--, j--) {
base *= i;
ans +=base;
}
return ans;
}

public static void main(String[] args) {
CountNumbersWithUniqueDigits slu = new CountNumbersWithUniqueDigits();
Assert.assertTrue("0", slu.countNumbersWithUniqueDigits(0), 1);
Assert.assertTrue("1", slu.countNumbersWithUniqueDigits(1), 10);
Assert.assertTrue("2", slu.countNumbersWithUniqueDigits(2), 9*9 + 10);
Assert.assertTrue("3", slu.countNumbersWithUniqueDigits(3), 9*9*8 + 9*9 + 10);
Assert.assertTrue("4", slu.countNumbersWithUniqueDigits(4), 9*9*8*7 + 9*9*8 + 9*9 + 10);
Assert.assertTrue("5", slu.countNumbersWithUniqueDigits(5), 9*9*8*7*6 + 9*9*8*7 + 9*9*8 + 9*9 + 10);
}
``````

• @laqxs LOL, yours is so damn "straight forward".

I think mine is much "straight forward" than yours:

``````if (n==0) return 1;
else if (n==1) return 10;
else if (n==2) return 91;
else if (n==3) return 739;
else if (n==4) return 5275;
else if (n==5) return 32491;
else if (n==6) return 168571;
else if (n==7) return 712891;
else if (n==8) return 2345851;
else if (n==9) return 5611771;
return 8877691;
``````

:-)

• @zhugejunwei
The "straightforward" I mentioned is for loop below not the testing main() method. You can skip the main() method.

``````    for(int i=9, j=n-1; i>0 && j>0; i--, j--) {
base *= i;
ans +=base;
}
``````

• @laqxs I was just kidding. )

• very similar to yours
Let f(k) = count of numbers with unique digits with length equals k.

f(1) = 10
f(2) = 9 * 9= 81 2 digits
f(3) = 9 * 9 * 8
f(4) = 9 * 9 * 8 * 7
....

public class Solution {

``````public int countNumbersWithUniqueDigits(int n) {
if (n==0)
return 1;
int sum  =10;
int q = 9;
for (int i =1; i<n; i++){
q *= (10-i);
sum += q;
}

return sum;
}
``````

}

• @zhugejunwei
interesting

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.