Python solution with detailed explanation


  • 0
    G

    Solution

    Count Numbers with Unique Digits https://leetcode.com/problems/count-numbers-with-unique-digits/?tab=Description

    Brute Force

    • Brute force will be to generate each number and test whether it has unique digits or not.
    • Boundary Condition: What happens when n is more than 10? Unique numbers are limited to the case of n = 10.
    • Split the problem in this view. Say N = 4. 0<=x<=9999.
    • This means that: [0, 1 to 9, 10 to 99, 100 to 999, 1000 to 9999].
    • Now implement backtracking for each of these ranges and keep adding to count.
    class Solution(object):
        def helper(self, i, dedup, n):
            if i == n:
                return 1
            else:
                count = 0
                start = 1 if i == 0 else 0
                for x in range(start,10):
                    if x not in dedup:
                        dedup.add(x)
                        count = count + self.helper(i+1, dedup, n)
                        dedup.remove(x)
            return count
        
        def countNumbersWithUniqueDigits(self, n):
            """
            :type n: int
            :rtype: int
            """
            count = 0
            for j in range(0, n+1):
                count = count + self.helper(0, set([]), j)
            return count
    

    Dynamic Programming

    • Next you can improve backtracking by dynamic programming. Assume you want to know all unique digit numbers from 100 to 999. First place can take 9 (1 to 9). Second place can take 9 (0 to 9 but not what we took in first place). Last place can take only 8.
      https://goo.gl/photos/oLz3dmPimXBgWWsDA

    Example: n=4

    • n = 1 temp = 9
    • n = 2 temp = 9 * 9
    • n=3 temp = 9 * 9 * 8
    • n=4 temp = 9 * 9 * 8 * 7
    class Solution(object):
        def countNumbersWithUniqueDigits(self, n):
            """
            :type n: int
            :rtype: int
            """
            soln, temp, factor = 1, 1, 9
            for i in range(n):
                temp = temp * factor
                soln = soln + temp
                factor = factor-1 if i!=0 else factor
            return soln
    

Log in to reply
 

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