0ms O(1) space C++ DP solution


  • 0
    W

    O(1) space:

    int countNumbersWithUniqueDigits(int n) {
                if ( n < 0 )  return 0;
                int result = 1;
                int multiplier = 9;
                n = min(n, 10);
                for (int i = 1; i <= n; i++) {
                    result += multiplier;
                    multiplier *= (i > 9 ? 0: (10 - i));
                }
                return result;
            }
    

    O(n) space:

     class Solution {
        public:
            int countNumbersWithUniqueDigits(int n) {
                if ( n < 0 )  return 0;
                vector<int> result(n+1);
                result[0] = 1;
                int multiplier = 9;
                n = min(n, 10);
                for (int i = 1; i <= n; i++) {
                    result[i] = result[i-1] + multiplier;
                    multiplier *= (i > 9 ? 0: (10 - i));
                }
                return result[n];
            }
        };

  • 0
    I

    The loop doesn't have to go n times, it only needs 10 times at most.


  • 0
    W

    yes you are right.


  • 0
    W

    added a "n = min(n, 10);", thanks for pointing out.


  • 0
    M

    why do you call it DP?


Log in to reply
 

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