Problem

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

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

1
2

Input: n = 1000
Output: 262

Constraints

  • 1 <= n <= 109

Solution

Method 1 – Digit DP (Count Unique Digits, Subtract)

Intuition

Count numbers with all unique digits up to n using digit DP, then subtract from n to get numbers with repeated digits.

Approach

  1. Convert n to a string for digit-wise processing.
  2. For numbers with fewer digits than n, count all unique-digit numbers using permutations.
  3. For numbers with the same number of digits as n, use digit DP:
    • Track used digits with a bitmask.
    • For each position, try all possible digits, ensuring no repeats and not exceeding n.
  4. Subtract the count of unique-digit numbers from n to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        vector<int> digits;
        int x = n;
        while (x) {
            digits.push_back(x % 10);
            x /= 10;
        }
        reverse(digits.begin(), digits.end());
        int k = digits.size(), ans = 0;
        // Count unique-digit numbers with length < k
        for (int i = 1; i < k; ++i) {
            int cnt = 9;
            for (int j = 1; j < i; ++j) cnt *= (10-j);
            ans += cnt;
        }
        // Count unique-digit numbers with length == k
        function<int(int, int, bool, bool)> dfs = [&](int pos, int mask, bool tight, bool leading) -> int {
            if (pos == k) return leading ? 1 : 0;
            int res = 0;
            int up = tight ? digits[pos] : 9;
            for (int d = 0; d <= up; ++d) {
                if (leading && d == 0) {
                    res += dfs(pos+1, mask, tight && d==up, true);
                } else if (!(mask & (1<<d))) {
                    res += dfs(pos+1, mask | (1<<d), tight && d==up, false);
                }
            }
            return res;
        };
        ans += dfs(0, 0, true, true);
        return n - ans + 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

func numDupDigitsAtMostN(n int) int {
    digits := []int{}
    x := n
    for x > 0 {
        digits = append([]int{x%10}, digits...)
        x /= 10
    }
    k, ans := len(digits), 0
    cnt := 1
    for i := 1; i < k; i++ {
        cnt = 9
        for j := 1; j < i; j++ {
            cnt *= (10-j)
        }
        ans += cnt
    }
    var dfs func(pos, mask int, tight, leading bool) int
    dfs = func(pos, mask int, tight, leading bool) int {
        if pos == k {
            if leading {
                return 1
            }
            return 0
        }
        res := 0
        up := 9
        if tight {
            up = digits[pos]
        }
        for d := 0; d <= up; d++ {
            if leading && d == 0 {
                res += dfs(pos+1, mask, tight && d==up, true)
            } else if mask&(1<<d) == 0 {
                res += dfs(pos+1, mask|(1<<d), tight && d==up, false)
            }
        }
        return res
    }
    ans += dfs(0, 0, true, true)
    return n - ans + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int numDupDigitsAtMostN(int n) {
        List<Integer> digits = new ArrayList<>();
        int x = n;
        while (x > 0) {
            digits.add(0, x % 10);
            x /= 10;
        }
        int k = digits.size(), ans = 0;
        for (int i = 1; i < k; ++i) {
            int cnt = 9;
            for (int j = 1; j < i; ++j) cnt *= (10-j);
            ans += cnt;
        }
        // DP
        ans += dfs(0, 0, true, true, digits);
        return n - ans + 1;
    }
    private int dfs(int pos, int mask, boolean tight, boolean leading, List<Integer> digits) {
        if (pos == digits.size()) return leading ? 1 : 0;
        int res = 0, up = tight ? digits.get(pos) : 9;
        for (int d = 0; d <= up; ++d) {
            if (leading && d == 0) {
                res += dfs(pos+1, mask, tight && d==up, true, digits);
            } else if ((mask & (1<<d)) == 0) {
                res += dfs(pos+1, mask | (1<<d), tight && d==up, false, digits);
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    fun numDupDigitsAtMostN(n: Int): Int {
        val digits = mutableListOf<Int>()
        var x = n
        while (x > 0) {
            digits.add(0, x % 10)
            x /= 10
        }
        val k = digits.size
        var ans = 0
        for (i in 1 until k) {
            var cnt = 9
            for (j in 1 until i) cnt *= (10-j)
            ans += cnt
        }
        fun dfs(pos: Int, mask: Int, tight: Boolean, leading: Boolean): Int {
            if (pos == k) return if (leading) 1 else 0
            var res = 0
            val up = if (tight) digits[pos] else 9
            for (d in 0..up) {
                if (leading && d == 0) {
                    res += dfs(pos+1, mask, tight && d==up, true)
                } else if (mask and (1 shl d) == 0) {
                    res += dfs(pos+1, mask or (1 shl d), tight && d==up, false)
                }
            }
            return res
        }
        ans += dfs(0, 0, true, true)
        return n - ans + 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        digits = list(map(int, str(n)))
        k, ans = len(digits), 0
        for i in range(1, k):
            cnt = 9
            for j in range(1, i):
                cnt *= (10-j)
            ans += cnt
        def dfs(pos: int, mask: int, tight: bool, leading: bool) -> int:
            if pos == k:
                return 1 if leading else 0
            res = 0
            up = digits[pos] if tight else 9
            for d in range(0, up+1):
                if leading and d == 0:
                    res += dfs(pos+1, mask, tight and d==up, True)
                elif not (mask & (1<<d)):
                    res += dfs(pos+1, mask | (1<<d), tight and d==up, False)
            return res
        ans += dfs(0, 0, True, True)
        return n - ans + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn num_dup_digits_at_most_n(n: i32) -> i32 {
        let mut digits = vec![];
        let mut x = n;
        while x > 0 {
            digits.insert(0, x % 10);
            x /= 10;
        }
        let k = digits.len();
        let mut ans = 0;
        for i in 1..k {
            let mut cnt = 9;
            for j in 1..i {
                cnt *= 10-j;
            }
            ans += cnt;
        }
        fn dfs(pos: usize, mask: i32, tight: bool, leading: bool, digits: &Vec<i32>) -> i32 {
            if pos == digits.len() {
                return if leading { 1 } else { 0 };
            }
            let mut res = 0;
            let up = if tight { digits[pos] } else { 9 };
            for d in 0..=up {
                if leading && d == 0 {
                    res += dfs(pos+1, mask, tight && d==up, true, digits);
                } else if mask & (1<<d) == 0 {
                    res += dfs(pos+1, mask | (1<<d), tight && d==up, false, digits);
                }
            }
            res
        }
        ans += dfs(0, 0, true, true, &digits);
        n - ans + 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    numDupDigitsAtMostN(n: number): number {
        const digits = Array.from(String(n), Number)
        const k = digits.length
        let ans = 0
        for (let i = 1; i < k; ++i) {
            let cnt = 9
            for (let j = 1; j < i; ++j) cnt *= (10-j)
            ans += cnt
        }
        function dfs(pos: number, mask: number, tight: boolean, leading: boolean): number {
            if (pos === k) return leading ? 1 : 0
            let res = 0
            const up = tight ? digits[pos] : 9
            for (let d = 0; d <= up; ++d) {
                if (leading && d === 0) {
                    res += dfs(pos+1, mask, tight && d===up, true)
                } else if ((mask & (1<<d)) === 0) {
                    res += dfs(pos+1, mask | (1<<d), tight && d===up, false)
                }
            }
            return res
        }
        ans += dfs(0, 0, true, true)
        return n - ans + 1
    }
}

Complexity

  • ⏰ Time complexity: O(k * 2^10) — k is the number of digits in n, 2^10 for bitmask.
  • 🧺 Space complexity: O(k * 2^10) — For recursion stack and bitmask DP.