# JAVA DP O(1) solution.

• Following the hint. Let f(n) = count of number with unique digits of length n.

f(1) = 10. (0, 1, 2, 3, ...., 9)

f(2) = 9 * 9. Because for each number i from 1, ..., 9, we can pick j to form a 2-digit number ij and there are 9 numbers that are different from i for j to choose from.

f(3) = f(2) * 8 = 9 * 9 * 8. Because for each number with unique digits of length 2, say ij, we can pick k to form a 3 digit number ijk and there are 8 numbers that are different from i and j for k to choose from.

Similarly f(4) = f(3) * 7 = 9 * 9 * 8 * 7....

...

f(10) = 9 * 9 * 8 * 7 * 6 * ... * 1

f(11) = 0 = f(12) = f(13)....

any number with length > 10 couldn't be unique digits number.

The problem is asking for numbers from 0 to 10^n. Hence return f(1) + f(2) + .. + f(n)

As @4acreg suggests, There are only 11 different ans. You can create a lookup table for it. This problem is O(1) in essence.

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

int res = 10;
int uniqueDigits = 9;
int availableNumber = 9;
while (n-- > 1 && availableNumber > 0) {
uniqueDigits = uniqueDigits * availableNumber;
res += uniqueDigits;
availableNumber--;
}
return res;
}``````

• What?How can it be? for f(1), 10 should be considered different digits, right?
0<=x<=10^1; that is 0<=x<=10; that is
for n = 1, f(1)=11, but 10 expected?

• The problem description was just revised, please check that out.

• You have `O(1)` solution not `O(n)`

Since you have `availableNumber > 0` condition in `while` loop. It iterates at most 9 times.

`O(9) -> O(1)`

• Yes Thanks for reminding me. This problem is O(1) in essence. There are only 11 different ans. You can create a lookup table.

• `enter code here`

``````public int countNumbersWithUniqueDigits(int n) {

if( n == 0 ){
return 1;
}

if( n == 1 ){
return 10;
}

if( n >= 10 ){
return 0;
}

int current = 81; // n == 2;  f(n) = f(n-1)*(11-n);
int total = 91;   // n == 2;
for(int i = 3 ; i <= n; i++){
current *= (11-i);
total += current;
}

}
``````

`enter code here`

• Concise code! But there is a small mistake. When n = 10 and beyond, it should return 8877691, not 0.

• Yes! you are correct, when n>=10, it should be the maximum number of unique digits numbers. thank you

• Mine is similar to yours but in C++.

``````class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(!n) return 1;
int res=10,mutil=9;
n=n>10?10:n;
for(int i=1;i<n;i++){
mutil*=10-i;
res+=mutil;
}
return res;
}
};
``````

• Hey dude! it is --n instead of n-- for the line while (n-- > 1 && availableNumber > 0). Please check once!

• @fatalme the question says the range should be 0<=x<10^1; that is 0<=x<10; 10 is not included.

• AC solution for c++ version with same idea

``````    int countNumbersWithUniqueDigits(int n) {
if(!n) return 1;
int res = 10, cur = 9, avail = 9;
while(--n && avail) res += (cur *= (avail--));
return res;
}
``````

• @fatalme it's 0<=x<10^n

• I will just call this math instead of dp, it's just a math problem.

• Similar idea, here is my lookup (not really) version:

``````class Solution {
public int countNumbersWithUniqueDigits(int n) {
int[] counts = new int[11];
if (n == 0)
return 1;   //tricky corner case
counts[1] = 10;
for (int i = 2; i < 11; i++)
counts[i] = 9 * permute(9, i - 1);
int res = 0;
for (int i = 1; i <= n; i++)
res += counts[i];
return res;
}

public int permute(int n, int k) {
int res = 1;
for (int i = 0; i < k; i++)
res *= n--;
return res;
}
}
``````

The method `permute(n, k)` computes `P(n, k)` as defined in combinatorics: number of ways to arrange k different numbers in n consecutive slots.

• ``````public int countNumbersWithUniqueDigits(int n) {
if (n==0){
return 1;
}
if (n>10){
return countNumbersWithUniqueDigits(10);
}
int sum = 1;
int k =0;
while(k<n){
if(k==0){
sum*=9;
}else{
sum*=(10-k);
}
k++;
}
return sum+countNumbersWithUniqueDigits(n-1);
}``````

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