JAVA DP O(1) solution.


  • 88
    S

    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;
        }

  • 1
    F

    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?


  • 0

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


  • 2
    4

    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)


  • 0
    S

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


  • 1
    T

    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;
        }
        
        return total;
    }
    

    enter code here


  • 2
    C

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


  • 0
    T

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


  • 1
    D

    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;
        }
    };
    

  • 0
    L

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


  • 0
    S

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


  • 0
    S

    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;
        }
    

  • 0
    L

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


  • 0
    M

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


Log in to reply
 

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