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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

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

Solutions:
class Solution:

	def numDupDigitsAtMostN(self, N: int) -> int:
		(NN, dd) = (N, 0)
		nums = []
		while NN:
			dd += 1
			nums.append(NN % 10)
			NN //= 10
		nums.reverse()
		numbers = 0
		for i in range(dd - 1):
			numbers += 9 * (math.factorial(9) // math.factorial(9 - i))
		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:
				break
			already_visited_digits.add(n)
		return N - numbers


class Solution:

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

		def numPerm(n, r):
			return math.factorial(n) // math.factorial(n - r)
		nums = [int(d) for d in str(N + 1)]
		K = len(nums)
		cnt = 0
		for i in range(1, K):
			cnt += 9 * numPerm(9, i - 1)
		seen = set()
		for i in range(K):
			for x in range(1 if i == 0 else 0, nums[i]):
				if x in seen:
					continue
				cnt += numPerm(10 - (i + 1), K - (i + 1))
			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
		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)
		return N - v


class Solution:

	def numDupDigitsAtMostN(self, N: int) -> int:
		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
			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


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
				return res
			if not lz:
				res = dfs(state, 10 ** (n - 1) - 1)
			elif 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)
			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)
					elif 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)
			return ret
		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
			elif i == n - 1:
				d += 1
		return N - d


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):
			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))
		return N - res