# 1012. Numbers With Repeated Digits

## Description

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Example 1:

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


Example 2:

Input: n = 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: n = 1000
Output: 262


Constraints:

• 1 <= n <= 109

## Solutions

• class Solution {
private int[] nums = new int[11];
private Integer[][] dp = new Integer[11][1 << 11];

public int numDupDigitsAtMostN(int n) {
return n - f(n);
}

private int f(int n) {
int i = -1;
for (; n > 0; n /= 10) {
nums[++i] = n % 10;
}
return dfs(i, 0, true, true);
}

if (pos < 0) {
return lead ? 0 : 1;
}
}
int ans = 0;
int up = limit ? nums[pos] : 9;
for (int i = 0; i <= up; ++i) {
if ((mask >> i & 1) == 1) {
continue;
}
if (i == 0 && lead) {
ans += dfs(pos - 1, mask, lead, limit && i == up);
} else {
ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
}
}
}
return ans;
}
}

• class Solution {
public:
int numDupDigitsAtMostN(int n) {
return n - f(n);
}

private:
int nums[11];
int dp[11][1 << 11];

int f(int n) {
memset(dp, -1, sizeof(dp));
int i = -1;
for (; n; n /= 10) {
nums[++i] = n % 10;
}
return dfs(i, 0, true, true);
}

if (pos < 0) {
return lead ? 0 : 1;
}
}
int up = limit ? nums[pos] : 9;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (mask >> i & 1) {
continue;
}
if (i == 0 && lead) {
ans += dfs(pos - 1, mask, lead, limit && i == up);
} else {
ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
}
}
}
return ans;
}
};

• class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
return n - self.f(n)

def f(self, n: int) -> int:
@cache
if pos < 0:
up = nums[pos] if limit else 9
ans = 0
for i in range(up + 1):
if mask >> i & 1:
continue
if i == 0 and lead:
ans += dfs(pos - 1, mask, lead, limit and i == up)
else:
ans += dfs(pos - 1, mask | 1 << i, False, limit and i == up)
return ans

nums = []
while n:
nums.append(n % 10)
n //= 10
return dfs(len(nums) - 1, 0, True, True)


• func numDupDigitsAtMostN(n int) int {
return n - f(n)
}

func f(n int) int {
nums := []int{}
for ; n > 0; n /= 10 {
nums = append(nums, n%10)
}
dp := [11][1 << 11]int{}
for i := range dp {
for j := range dp[i] {
dp[i][j] = -1
}
}
var dfs func(int, int, bool, bool) int
dfs = func(pos int, mask int, lead bool, limit bool) int {
if pos < 0 {
return 0
}
return 1
}
}
up := 9
if limit {
up = nums[pos]
}
ans := 0
for i := 0; i <= up; i++ {
continue
}
if i == 0 && lead {
} else {
ans += dfs(pos-1, mask|1<<i, false, limit && i == up)
}
}
}
return ans
}
return dfs(len(nums)-1, 0, true, true)
}

• function numDupDigitsAtMostN(n: number): number {
return n - f(n);
}

function f(n: number): number {
const nums: number[] = [];
let i = -1;
for (; n; n = Math.floor(n / 10)) {
nums[++i] = n % 10;
}
const dp = Array.from({ length: 11 }, () => Array(1 << 11).fill(-1));
const dfs = (pos: number, mask: number, lead: boolean, limit: boolean): number => {
if (pos < 0) {
return lead ? 0 : 1;
}
}
const up = limit ? nums[pos] : 9;
let ans = 0;
for (let i = 0; i <= up; ++i) {
if ((mask >> i) & 1) {
continue;
}
if (lead && i === 0) {
ans += dfs(pos - 1, mask, lead, limit && i === up);
} else {
ans += dfs(pos - 1, mask | (1 << i), false, limit && i === up);
}
}