c++ 0ms solution using math and DP with explaination


  • 1
    J

    1 unique digit number : dp[0]=10; 2 unique digits number: dp[1]=99 +dp[0]; 3 unique digits number:dp[2]= 998+dp[1]; 4 unique digits number: 9987+dp[2].... It only need memories for the dp[i-1], optimize it with O(1) space.

     int countNumbersWithUniqueDigits(int n) {        
            if(n==0)
                return 1;
            if(n==1)
                return 10;    
            
            int cur=10;
            int prev=0;
            for(int i=2; i<=n; i++)
            {
                int val=9;
                prev=cur;
                for(int j=0; j<i-1; j++)
                {
                    val*=(9-j);
                }
                cur=val+prev;
            }
            return cur;
        }
    

  • 0
    C

    This is a good solution but the double loop is unnecessary and is detrimental to performance.

    It's easy to get rid of the inner loop:

        int countNumbersWithUniqueDigits(int n) {
            if(n==0)
                return 1;
            if(n==1)
                return 10;    
            
            int cur=10;
            int val=9;
            for(int i=2; i<=n; i++)
            {
                val *= 9 - i + 2;
                cur += val;
            }
            return cur;
        }
    

    Runtime goes from 3 ms to 0 ms.


Log in to reply
 

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