C++ solution with single loop


  • 0
    A
    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {
            //dp[k] : count of unique k-digit numbers
            //zeros[k] : count of unique k-digit numbers with 0
            //non_zeros[k] : count of unique k-digit numbers without 0
            //dp[k] = zeros[k] + non_zeros[k]
            //zeros[k] = (k-1) * non_zeros[k-1]
            //non_zeros[k] = (10 - k) * non_zeros[k-1]
            
            //optimization: use z for zeros[k-1] and nz for non_zeros[k-1], res as the sum of dp[i] for i in [1...n]
            if (!n) return 1;
            int z = 1, nz = 9, res = 10;
            for (int i = 2; i <= n; ++i) {
                z = (i - 1) * nz;
                nz = (10 - i) * nz
                res += z + nz;
            }
            return res;
        }
    };
    

Log in to reply
 

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