Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.
 

Example 1:
Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.


Example 2:
Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.


Example 3:
Input: 1000
Output: 262


 
Note:

1 <= N <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        

Solutions:
class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        # N -> total numbers less than or equal to N
        # We will calculate the integers with all different digits (which are less than/equal to N)
        # Then the answer would be: N - nums_with_different_digits
        
        # Calculate the number of digits in N
        NN, dd = N, 0
        nums = [] # store the digits
        while(NN):
            dd += 1
            nums.append(NN % 10)
            NN //= 10
        nums.reverse()
        
        
        # numbers with less digits than that of N
        numbers = 0
        for i in range(dd-1):
            numbers += 9 * (math.factorial(9) // math.factorial(9-i))
        
        
        # find the N-digit numbers (all-different)
        already_visited_digits = set()
        
        def fac2(n, k):
            return math.factorial(n) // math.factorial(n-k)
        
        for i,n in enumerate(nums):
            k = 0
            for j in range((1 if i==0 else 0), (n+1 if i==dd-1 else n)):
                if(j in already_visited_digits):
                    continue
                k += 1
            numbers += k * fac2(10-i-1, dd-i-1)
            if n in already_visited_digits:
                # All the numbers with this prefix will have at least one common digit
                break
            already_visited_digits.add(n)
            
        return N - numbers

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        ## https://leetcode.com/problems/numbers-with-repeated-digits/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit
#     \"\"\"
#     The corner case is too hard to manage...

#     count res as N - total number without duplicated digits.
#     turns into a math and permutation problem.

#     select m out of n
#     P(m, n): n! / (n-m)!

#     Algorithm:

#     lets say N has k digits.
#     1) count number less than k digits
#     lets say number with i digits
#     first digit 1 ~ 9, following option is 0 ~ 9 without first digit
#     count = 9 * P(i-1,9)

#     2) count number has k digits. 
#     Calculate digits with same prefix. 
#     Prefix cannot has duplicate digits.
#     for case like 77xxx, we should stop the calculation.
#     \"\"\"
        
        def numPerm(n, r):
            return math.factorial(n)//math.factorial(n-r)
        
        
        # N + 1 as padding.
        nums = [int(d) for d in str(N + 1)]
        K = len(nums) # N has K digits
        cnt = 0 # number with no repeated val
         # count **postive number with digits less than K
        for i in range(1, K):
            cnt += 9*numPerm(9, i-1)
            
        # count number with K digits
        seen = set() # seen digit
        for i in range(K): 
            # prefix = nums[:i] + currentDigit
            # currentDigit < nums[i]
            for x in range(1 if i == 0 else 0, nums[i]):
                if x in seen: continue # avoid duplication
                # cnt += P(K - (i + 1), 10 - (i + 1))
                cnt += numPerm(10 - (i + 1), K - (i + 1))
            
            # since next iteration, prefix has duplicate digits, break
            if nums[i] in seen: break
            seen.add(nums[i])
        
        return N - cnt
        
       
        


class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        k = 0
        num = []
        t = N
        while t:
            num.append(t%10)
            t = t//10
            k += 1
        num = num[::-1]
        digits = [i for i in range(10)]
        dp = [[0 for _ in range(2)] for _  in range(k+1)]
        def count(dp, dig, state, d1, seen):
            if dig == k:
                return 1
            if dp[dig][state]:
                return dp[dig][state]
            
            seen.add(d1)
            for d in digits:
                if d in seen:
                    continue
                if state == 0:
                    dp[dig][state] += count(dp, dig + 1, state, d, seen)
                elif state == 1:
                    if d > num[dig]:
                        continue
                    if d < num[dig]:
                        dp[dig][state] += count(dp, dig + 1, state^1, d, seen)
                    elif d == num[dig]:
                        dp[dig][state] += count(dp, dig + 1, state, d, seen)
            
            seen.remove(d1)
            return dp[dig][state]
        
        v = 0
        # print(k)
        for d in range(1, 10):
            seen = set()
            if d < num[0]:
                v += count(dp, 1, 0, d, seen)
            elif d == num[0]:
                v += count(dp, 1, 1, d, seen)
        
        
        for i in range(1, k):
            for p in range(1, 10):
                seen = set()
                dp = [[0 for _ in range(2)] for _  in range(k+1)]
                v += count(dp, i + 1, 0, p, seen)
            # print(v)
        # print(dp[3][0])
        return N - v 

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        # https://leetcode.com/problems/numbers-with-repeated-digits/discuss/592922/Python-Well-commented-solution-with-easy-to-follow-recursion   
        memo = {}
        def f(digits_of_N, i, digits_used, any_digit):
            if i == k:
                return 1
            
            key = (i, digits_used, any_digit)
            if key in memo:
                return memo[key]
            cnt = 0
            min_digit = 1 if i == 0 else 0
            max_digit = 9 if any_digit else digits_of_N[i]
            for d in range(min_digit, max_digit + 1):
                if digits_used & (1 << d) != 0:
                    continue
                cnt += f(digits_of_N, i + 1, digits_used | (1 << d), any_digit or (d < digits_of_N[i]))
            
            memo[key] = cnt
            return cnt
        if N <= 9:
            return 0
        k = len(str(N))
        cnt = 0
        for i in range(1, k):
            all_possible_ints = 9 * 10**(i-1)
            ints_with_unique_digits = 9
            nb_choices = 9
            for j in range(1, i):
                ints_with_unique_digits *= nb_choices
                nb_choices -= 1
            cnt += all_possible_ints - ints_with_unique_digits
            
        all_ints_with_k_digits = N - int('9'*(k-1))
        digits_of_N = [int(d) for d in str(N)]
        ints_with_unique_k_digits = f(digits_of_N, 0, 0, False)
        cnt += all_ints_with_k_digits - ints_with_unique_k_digits
        
        return cnt

def f(n,s,e,ci,di,v):
    if n==ci:
        return 1
    a=0
    if (e,ci,v) in di:
        return di[e,ci,v]
    for i in range(10):
            if e==0:
                if not v>>i&1:
                    eee=v|(1<<i)
                    a+=f(n,s,0,ci+1,di,eee)
            else:
                if i>int(s[ci]):
                    break
                if int(s[ci])==i:
                    if not v>>i&1:
                        eee=v|(1<<i)
                        a+=f(n,s,1,ci+1,di,eee)
                    break
                if not v>>i&1:
                    eee=v|(1<<i)
                    a+=f(n,s,0,ci+1,di,eee)
    di[e,ci,v]=a
    return a
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        if n<=10:
            return 0
        s=str(n)
        l=len(s)
        ans=10
        prev=9
        for i in range(9,9-l+2,-1):
            ans+= prev*i
            prev=prev*i
        a=0
        di={}
        v=0
        for i in range(1,10):
            if i>int(s[0]):
                break
            if i==int(s[0]):
                e=1<<i
                a+=f(l,s,1,1,di,e)
                break
            e=1<<i
            a+=f(l,s,0,1,di,e)
        return n-a-ans+1

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        digits = []
        M=N+1
        while M>0:
            digits.append(M%10)
            M//=10
            
        part_1 = 0
        prod=9
        i_1=9
        
        n = len(digits)
        
        for i in range(n-1):
            part_1+=prod
            # print(i,part_1,prod)
            if i_1>1:
                if i>0:
                    i_1-=1
                prod*=i_1
        i_1=9
        seen = set([])
        cols = [0 for i in range(10)]
        while len(digits)>0:
            digit = digits.pop()
            if len(digits)==n-1:
                prod = digit-1
            else:
                prod = digit-cols[digit]
            j_1=i_1
            for i in range(len(digits)):
                prod*=j_1
                j_1-=1
            i_1-=1
            part_1+=prod
            
            if digit in seen:
                break
            else:
                seen.add(digit)
            for i in range(digit+1,10):
                cols[i]+=1
        return N -part_1

def f(n,s,e,ci,di,v):
    if n==ci:
        return 1
    a=0
    if (e,ci,v) in di:
        return di[e,ci,v]
    for i in range(10):
            if e==0:
                if not v>>i&1:
                    eee=v|(1<<i)
                    a+=f(n,s,0,ci+1,di,eee)
            else:
                if i>int(s[ci]):
                    break
                if int(s[ci])==i:
                    if not v>>i&1:
                        eee=v|(1<<i)
                        a+=f(n,s,1,ci+1,di,eee)
                    break
                if not v>>i&1:
                    eee=v|(1<<i)
                    a+=f(n,s,0,ci+1,di,eee)
    di[e,ci,v]=a
    return a
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        if n<=10:
            return 0
        s=str(n)
        l=len(s)
        ans=10
        prev=9
        for i in range(9,9-l+2,-1):
            ans+= prev*i
            prev=prev*i
        a=0
        di={}
        v=0
        for i in range(1,10):
            if i>int(s[0]):
                break
            if i==int(s[0]):
                e=1<<i
                a+=f(l,s,1,1,di,e)
                break
            e=1<<i
            a+=f(l,s,0,1,di,e)
        return n-a-ans+1


class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        N = str(N)
        
        @lru_cache(None)
        def dfs(i, r, m):
            if i == len(N):
                return 1
            
            ans = 0
            limit = int(N[i]) if r else 9
            for k in range(0,limit+1):
                if m & (1 << k) == 0:
                    mask =  m | (1 << k) if m or k > 0 else 0
                    if k < limit or not r:
                        ans += dfs(i+1, False, mask)
                    else:
                        ans += dfs(i+1, True, mask)
            return ans
        
        return int(N) - dfs(0, True, 0) + 1

from functools import lru_cache
class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        @lru_cache(None)
        def dfs(state, x, lz=False):
            n = len(str(x))
            if x < 10:
                res = 0
                if not lz:
                    for i in range(1, x + 1):
                        if state & (1 << i) == 0:
                            res += 1
                else:
                    for i in range(x + 1):
                        if state & (1 << i) == 0:
                            res += 1
                # print(bin(state), x, lz, res)
                return res
            if not lz:
                res = dfs(state, 10 ** (n - 1) - 1)
            else:
                if state & 1 == 0:
                    res = dfs(state | 1, 10 ** (n - 1) - 1, True)
                else:
                    res = 0
            for i in range(1, int(str(x)[0])):
                if state & (1 << i) == 0:
                    res += dfs(state | (1 << i), 10 ** (n - 1) - 1, True)
            if state & (1 << int(str(x)[0])) == 0:
                if not (x % 10 ** (n - 1) == 0 and n >= 3):
                    if x % 10 ** (n - 1) >= 10 ** (n - 2) or n <= 2:
                        res += dfs(state | (1 << int(str(x)[0])), x % 10 ** (n - 1), True)
                    elif n >= 3 and 1 & state == 0 and x % 10 ** (n - 1) >= 10 ** (n - 3):
                        res += dfs(state | (1 << int(str(x)[0])) + 1, x % 10 ** (n - 1), True)
            # print(bin(state), x, lz, res)
            return res
        
        return N - dfs(0, N)


class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        @lru_cache(None)
        def dp(i, smaller, nonzero, used):
            if i==len(s):
                return nonzero
            ret = 0
            if smaller:
                for dig in range(10):
                    if dig==0 and not nonzero:
                        ret += dp(i+1, True, False, used)
                    else:
                        if (1<<dig)&used:
                            continue
                        ret += dp(i+1, True, True, used|(1<<dig))
            else:
                for dig in range(10):
                    if dig>int(s[i]):
                        break
                    elif dig==int(s[i]):
                        if (1<<dig)&used:
                            continue
                        ret += dp(i+1, False, True, used|(1<<dig))
                    else:
                        if dig==0 and not nonzero:
                            ret += dp(i+1, True, False, used)
                        else:
                            if (1<<dig)&used:
                                continue
                            ret += dp(i+1, True, True, used|(1<<dig))
            # print(i, smaller, nonzero, bin(used), ret)
            return ret
        # print(dp(0, False, False, 0))
        return n - dp(0, False, False, 0)

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        L = list(map(int, str(N + 1)))
        res, n = 0, len(str(N + 1))

        def A(m, n):
            return 1 if n == 0 else A(m, n - 1) * (m - n + 1)

        for i in range(1, n): res += 9 * A(9, i - 1)
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += A(9 - i, n - i - 1)
            if x in s: break
            s.add(x)
        return N - res


class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        list_N = list(map(int, str(N + 1)))
        solution = 0
        def permutation(m, n):
            return 1 if n == 0 else permutation(m, n - 1) * (m - n + 1)
        for i in range(1, len(list_N)):
            solution += 9 * permutation(9, i - 1)
        seen_set = set()
        for i, x in enumerate(list_N):
            for y in range(0 if i else 1, x):
                if y not in seen_set:
                    solution += permutation(9 - i, len(list_N) - i - 1)
            if x in seen_set:
                break
            seen_set.add(x)
        return N - solution

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        if N < 100:
            return N // 11
        
        s = str(N)
        l = len(s)
        
        if l > 10:
            return N - 8877690
        
        mapping = {
         0:  0,
         1:  9,
         2:  90,
         3:  738,
         4:  5274,
         5:  32490,
         6:  168570,
         7:  712890,
         8:  2345850,
         9:  5611770,
         10: 8877690}
        
        seen = set()

        for i, d in enumerate(s):
            d = int(d)
            if d > 0:
                f = sum(1 for j in range((1 if i == 0 else 0), d) if j not in seen)
                for j in range(l-i-1):
                    f *= (9-i-j)
                N -= f
            
            if i == l - 1 and d not in seen:
                N -= 1
            if d in seen:
                break
            seen.add(d)
        return N - mapping[l-1]

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        digits = list(map(int, str(N)))
        n = len(digits)
        d = 0
        for i in range(1, n):
            d += 9 * math.factorial(9) // math.factorial(10 - i)
        for i, j in enumerate(digits):
            for k in range(1 if i == 0 else 0, j):
                if k in digits[:i]:
                    continue
                x = 10 - i - 1
                d += math.factorial(x) // math.factorial(x - (n - i - 1))
            if j in digits[:i]:
                break
            else:
                if i == n - 1:
                    d += 1
        return N - d

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
         # N -> total numbers less than or equal to N
        # We will calculate the integers with all different digits (which are less than/equal to N)
        # Then the answer would be: N - nums_with_different_digits
        
        # Calculate the number of digits in N
        NN, dd = N, 0
        nums = [] # store the digits
        while(NN):
            dd += 1
            nums.append(NN % 10)
            NN //= 10
        nums.reverse()
        
        
        # numbers with less digits than that of N
        numbers = 0
        for i in range(dd-1):
            numbers += 9 * (math.factorial(9) // math.factorial(9-i))
        
        
        # find the N-digit numbers (all-different)
        already_visited_digits = set()
        
        def fac2(n, k):
            return math.factorial(n) // math.factorial(n-k)
        
        for i,n in enumerate(nums):
            k = 0
            for j in range((1 if i==0 else 0), (n+1 if i==dd-1 else n)):
                if(j in already_visited_digits):
                    continue
                k += 1
            numbers += k * fac2(10-i-1, dd-i-1)
            if n in already_visited_digits:
                # All the numbers with this prefix will have at least one common digit
                break
            already_visited_digits.add(n)
            
        return N - numbers

def parcfact(m):
    return sum([fact(m1)    for m1 in range(1,m)])

def fact(m):
    p = 1;
    for ii in range(m):
        p = p*min(9,10-ii)
    return p


class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        found = {}
        NS = str(N)        
        res = parcfact(len(NS))
        found = {}
        def count(par):
#            print(par,len(par),NS)
            res = 0
            if len(par)==len(NS) and par<=NS:
                return 1
            elif len(par)<len(NS):
                for ii in range(10):
                    if par.find(str(ii))<0 and par+str(ii)<=NS[:len(par)+1]:
                        if par+str(ii)<NS[:len(par)+1]:
                            if not(len(par)) in found:
                                found[len(par)] = count(par+str(ii))
                            res = res+found[len(par)]
                        else:
                            res = res+count(par+str(ii))
            return res
        for ii in range(1,int(NS[0])+1):
            res = res+count(str(ii)) 
#        print(res,print(found))
        return(N-res)