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


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

Log in to reply
 

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