2376. Count Special Integers LeetCode Solution

Last updated: February 27, 2025

In this guide, you will get 2376. Count Special Integers LeetCode Solution with the best time and space complexity. The solution to Count Special Integers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Special Integers solution in C++
Count Special Integers solution in Java
Count Special Integers solution in Python
Additional Resources

2376. Count Special Integers LeetCode Solution image

Problem Statement of Count Special Integers

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].

Example 1:

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:

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

Example 3:

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 * 109

Complexity Analysis

Time Complexity: O(\log n \cdot 2^{10} \cdot 2 \cdot 10)
Space Complexity: O(\log n \cdot 2^{10} \cdot 2)

2376. Count Special Integers LeetCode Solution in C++

class Solution {
 public:
  // Same as 1012. Numbers With Repeated Digits
  int countSpecialNumbers(int n) {
    const int digitSize = log10(n) + 1;
    vector<vector<vector<int>>> mem(
        digitSize + 1, vector<vector<int>>(1 << 10, vector<int>(2, -1)));
    return count(to_string(n), 0, 0, true, mem) - 1;  // - 0;
  }

 private:
  // Returns the number of special integers, considering the i-th digit, where
  // `used` is the bitmask of the used digits, and `isTight` indicates if the
  // current digit is tightly bound.
  int count(const string& s, int i, int used, bool isTight,
            vector<vector<vector<int>>>& mem) {
    if (i == s.length())
      return 1;
    if (mem[i][used][isTight] != -1)
      return mem[i][used][isTight];

    int res = 0;
    const int maxDigit = isTight ? s[i] - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      // `d` is used.
      if (used >> d & 1)
        continue;
      // Use `d` now.
      const bool nextIsTight = isTight && (d == maxDigit);
      if (used == 0 && d == 0)  // Don't count leading 0s as used.
        res += count(s, i + 1, used, nextIsTight, mem);
      else
        res += count(s, i + 1, used | 1 << d, nextIsTight, mem);
    }

    return mem[i][used][isTight] = res;
  }
};
/* code provided by PROGIEZ */

2376. Count Special Integers LeetCode Solution in Java

class Solution {
  // Same as 1012. Numbers With Repeated Digits
  public int countSpecialNumbers(int n) {
    final int digitSize = (int) Math.log10(n) + 1;
    Integer[][][] mem = new Integer[digitSize + 1][1 << 10][2];
    return count(String.valueOf(n), 0, 0, true, mem) - 1; // - 0;
  }

  // Returns the number of special integers, considering the i-th digit, where
  // `used` is the bitmask of the used digits, and `isTight` indicates if the
  // current digit is tightly bound.
  private int count(final String s, int i, int used, boolean isTight, Integer[][][] mem) {
    if (i == s.length())
      return 1;
    if (mem[i][used][isTight ? 1 : 0] != null)
      return mem[i][used][isTight ? 1 : 0];

    int res = 0;
    final int maxDigit = isTight ? s.charAt(i) - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      // `d` is used.
      if ((used >> d & 1) == 1)
        continue;
      // Use `d` now.
      final boolean nextIsTight = isTight && (d == maxDigit);
      if (used == 0 && d == 0) // Don't count leading 0s as used.
        res += count(s, i + 1, used, nextIsTight, mem);
      else
        res += count(s, i + 1, used | 1 << d, nextIsTight, mem);
    }

    return mem[i][used][isTight ? 1 : 0] = res;
  }
}
// code provided by PROGIEZ

2376. Count Special Integers LeetCode Solution in Python

class Solution:
  # Same as 1012. Numbers With Repeated Digits
  def countSpecialNumbers(self, n: int) -> int:
    s = str(n)

    @functools.lru_cache(None)
    def dp(i: int, used: int, isTight: bool) -> int:
      """
      Returns the number of special integers, considering the i-th digit, where
      `used` is the bitmask of the used digits, and `isTight` indicates if the
      current digit is tightly bound.
      """
      if i == len(s):
        return 1

      res = 0
      maxDigit = int(s[i]) if isTight else 9

      for d in range(maxDigit + 1):
        # `d` is used.
        if used >> d & 1:
          continue
        # Use `d` now.
        nextIsTight = isTight and (d == maxDigit)
        if used == 0 and d == 0:  # Don't count leading 0s as used.
          res += dp(i + 1, used, nextIsTight)
        else:
          res += dp(i + 1, used | 1 << d, nextIsTight)

      return res

    return dp(0, 0, True) - 1  # - 0
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents