Count Numbers With Unique Digits II

Problem

Given two positive integers a and b, return the count of numbers having unique digits in the range [a, b] (inclusive).

Examples

Example 1:

1
2
3


Input: a = 1, b = 20
Output: 19
Explanation: All the numbers in the range [1, 20] have unique digits except 11. Hence, the answer is 19.

Example 2:

1
2
3


Input: a = 9, b = 19
Output: 10
Explanation: All the numbers in the range [9, 19] have unique digits except 11. Hence, the answer is 10. 

Example 3:

1
2
3


Input: a = 80, b = 120
Output: 27
Explanation: There are 41 numbers in the range [80, 120], 27 of which have unique digits.

Constraints:

1 <= a <= b <= 1000

Solution

Method 1 – Digit DP with Bitmask

Intuition

To count numbers with unique digits in a range, we use digit dynamic programming (digit DP) with state compression (bitmask). We count unique digit numbers up to b and subtract those up to a-1. The DP recursively builds numbers digit by digit, tracking used digits with a bitmask and respecting the upper bound with a limit flag. Memoization ensures efficiency.

Approach

For both bounds, convert the number to a string and use a DP table indexed by position and bitmask.
The recursive function dfs(pos, mask, limit):
- Returns 1 if a valid number is formed (mask > 0) at the end.
- For each digit, skip if already used (mask).
- For leading zeros, allow them but don’t set their bit in the mask.
- Use memoization for states where limit is false.
The answer is count(b) - count(a-1).

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


class Solution {
    private String num;
    private Integer[][] memo;
    public int countUniqueDigits(int a, int b) {
        num = String.valueOf(a - 1);
        memo = new Integer[num.length()][1 << 10];
        int lower = dfs(0, 0, true);
        num = String.valueOf(b);
        memo = new Integer[num.length()][1 << 10];
        int upper = dfs(0, 0, true);
        return upper - lower;
    }
    private int dfs(int pos, int mask, boolean limit) {
        if (pos == num.length()) return mask > 0 ? 1 : 0;
        if (!limit && memo[pos][mask] != null) return memo[pos][mask];
        int up = limit ? num.charAt(pos) - '0' : 9;
        int ans = 0;
        for (int d = 0; d <= up; ++d) {
            if ((mask >> d & 1) == 1) continue;
            int nextMask = (mask == 0 && d == 0) ? 0 : mask | (1 << d);
            ans += dfs(pos + 1, nextMask, limit && d == up);
        }
        if (!limit) memo[pos][mask] = ans;
        return ans;
    }
}

 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


class Solution {
public:
    string num;
    int dp[12][1<<10];
    int dfs(int pos, int mask, bool limit) {
        if (pos == num.size()) return mask > 0 ? 1 : 0;
        if (!limit && dp[pos][mask] != -1) return dp[pos][mask];
        int up = limit ? num[pos] - '0' : 9, ans = 0;
        for (int d = 0; d <= up; ++d) {
            if ((mask >> d) & 1) continue;
            int nextMask = (mask == 0 && d == 0) ? 0 : mask | (1 << d);
            ans += dfs(pos + 1, nextMask, limit && d == up);
        }
        if (!limit) dp[pos][mask] = ans;
        return ans;
    }
    int countUniqueDigits(int a, int b) {
        num = to_string(a - 1);
        memset(dp, -1, sizeof dp);
        int lower = dfs(0, 0, true);
        num = to_string(b);
        memset(dp, -1, sizeof dp);
        int upper = dfs(0, 0, true);
        return upper - lower;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countUniqueDigits(self, a: int, b: int) -> int:
        def solve(n: int) -> int:
            s = str(n)
            from functools import lru_cache
            @lru_cache(None)
            def dfs(pos: int, mask: int, limit: bool) -> int:
                if pos == len(s):
                    return 1 if mask > 0 else 0
                up = int(s[pos]) if limit else 9
                ans = 0
                for d in range(0, up+1):
                    if (mask >> d) & 1: continue
                    nextMask = 0 if mask == 0 and d == 0 else mask | (1 << d)
                    ans += dfs(pos+1, nextMask, limit and d == up)
                return ans
            return dfs(0, 0, True)
        return solve(b) - solve(a-1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    fun countUniqueDigits(a: Int, b: Int): Int {
        fun solve(n: Int): Int {
            val s = n.toString()
            val memo = Array(s.length) { Array(1 shl 10) { -1 } }
            fun dfs(pos: Int, mask: Int, limit: Boolean): Int {
                if (pos == s.length) return if (mask > 0) 1 else 0
                if (!limit && memo[pos][mask] != -1) return memo[pos][mask]
                val up = if (limit) s[pos] - '0' else 9
                var ans = 0
                for (d in 0..up) {
                    if ((mask shr d) and 1 == 1) continue
                    val nextMask = if (mask == 0 && d == 0) 0 else mask or (1 shl d)
                    ans += dfs(pos+1, nextMask, limit && d == up)
                }
                if (!limit) memo[pos][mask] = ans
                return ans
            }
            return dfs(0, 0, true)
        }
        return solve(b) - solve(a-1)
    }
}

Complexity

⏰ Time complexity: O(d * 2^d), where d is the number of digits.
🧺 Space complexity: O(d * 2^d), for the DP memoization table.

Problem#

Examples#

Solution#

Method 1 – Digit DP with Bitmask#

Intuition#

Approach#

Code#

Complexity#