Problem

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval[1, n].

Examples

Example 1

1
2
3

Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Example 2

1
2
3

Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.

Example 3

1
2
3
4

Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

Constraints

  • 1 <= n <= 2 * 10^9

Solution

Method 1 – Digit DP (Bitmask Dynamic Programming)

Intuition

A number is special if all its digits are unique. We can use digit dynamic programming (DP) to count numbers with unique digits up to n, by processing each digit position, tracking which digits have been used (with a bitmask), and whether we are still tight to the upper bound.

Approach

  1. Convert n to a string for easy digit access.
  2. Define a DP function: dp(pos, mask, tight, leading_zero) where:
    • pos: current digit position
    • mask: bitmask of used digits
    • tight: whether the current prefix is equal to n’s prefix
    • leading_zero: whether we are still placing leading zeros
  3. For each position, try all possible digits:
    • If the digit is already used (mask), skip.
    • If tight, the digit cannot exceed the corresponding digit in n.
    • If not leading_zero, do not allow 0 as the first digit.
  4. Base case: if all positions are filled, return 1 if not leading_zero, else 0.
  5. Memoize the DP function.
  6. Call dp(0, 0, True, True).

Code

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

class Solution {
    public int countSpecialNumbers(int n) {
        String s = Integer.toString(n);
        int len = s.length();
        Integer[][][] dp = new Integer[len+1][1<<10][2];
        return dfs(0, 0, true, false, s, dp);
    }
    private int dfs(int pos, int mask, boolean tight, boolean leadingZero, String s, Integer[][][] dp) {
        if (pos == s.length()) return leadingZero ? 0 : 1;
        if (dp[pos][mask][tight ? 1 : 0] != null) return dp[pos][mask][tight ? 1 : 0];
        int res = 0, up = tight ? s.charAt(pos) - '0' : 9;
        for (int d = 0; d <= up; d++) {
            if ((mask == 0 && d == 0)) {
                res += dfs(pos+1, mask, tight && d == up, true, s, dp);
            } else if ((mask & (1 << d)) == 0) {
                res += dfs(pos+1, mask | (1 << d), tight && d == up, false, s, dp);
            }
        }
        return dp[pos][mask][tight ? 1 : 0] = res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
        from functools import lru_cache
        @lru_cache(None)
        def dp(pos: int, mask: int, tight: bool, leading_zero: bool) -> int:
            if pos == len(s):
                return 0 if leading_zero else 1
            res = 0
            up = int(s[pos]) if tight else 9
            for d in range(0, up+1):
                if mask == 0 and d == 0:
                    res += dp(pos+1, mask, tight and d == up, True)
                elif not (mask & (1 << d)):
                    res += dp(pos+1, mask | (1 << d), tight and d == up, False)
            return res
        return dp(0, 0, True, True)

Complexity

  • ⏰ Time complexity: O(L * 2^L), where L is the number of digits in n (since there are L positions and 2^10 bitmask states).
  • 🧺 Space complexity: O(L * 2^L), for the DP memoization table.