# Python solution with detailed explanation

• 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:
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
``````

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