Leetcode 357. Count Numbers with Unique Digits (Python)

Related Topic

Dynamic-Programming.

Description

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

Sample I/O

Example 1

Input: 2
Output: 91 
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100,
excluding 11,22,33,44,55,66,77,88,99

Methodology

This question can be solved by Dynamic Programming. However, dp is not the only best solution.

This question is really easy to find the base case and pattern, basiclly you need find the the number of unique digits in current range and add the previous number to get the current total unique digits.

Base case:

When n = 0, there is 1 and only digit so dp[0] = 1
when n = 1, there is 10 unqiue digits so dp[1] = 10

Pattern

Every time when the n increase 1, there will be split to two range. The previous range which is [10^0,10^n-1) and the current range which is [10^n-1, 10^n). The current range you can apply permutation on it. Because the first digit always has 9 options, second has 8 options, third has 7 options….until you reach to the last digit.

After you get the current unique digits, the total unique digits is unique digits in current range plus the unique digits in previous range.

Code 1

def countNumbersWithUniqueDigits(self, n: int) -> int:
        dp=[1]*(n+1)
        for i in range(1,n+1):    
            base = 9
            for digit in range(1, i):
                base = base*(10-digit)
            dp[i]=base+dp[i-1]
        return dp[-1]

BigO

We iterate the dp array, it will cost O(n+1), each iteration need to iterate O(n+1-1), so the total time complexity is O((n+1)/*n) which is O(n^2)