2376. Count Special Integers

Description

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(m*2¹⁰*10)
• Space complexity: O(m*2¹⁰)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const countSpecialNumbers = function (n) {
  const nums = `${n}`.split('').map(Number);
  const m = nums.length;
  const dp = Array.from({ length: m }, () => {
    return new Array(1 << 10).fill(-1);
  });

  const countSpecial = (index, isTight, mask) => {
    if (index >= m) return mask ? 1 : 0;

    if (!isTight && dp[index][mask] !== -1) {
      return dp[index][mask];
    }

    const limit = isTight ? nums[index] : 9;
    let result = 0;

    for (let num = 0; num <= limit; num++) {
      if (mask & (1 << num)) continue;

      if (mask === 0 && num === 0) {
        result += countSpecial(index + 1, false, mask);
        continue;
      }

      const nextTight = isTight && num === limit;
      const nextMask = mask | (1 << num);

      result += countSpecial(index + 1, nextTight, nextMask);
    }

    if (!isTight) {
      dp[index][mask] = result;
    }

    return result;
  };

  return countSpecial(0, true, 0);
};