[Solved] Count Special Integers LeetCode Contest 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].

Count Special Integers LeetCode Contest

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

Solution

class Solution {
public:
    int frac[11];
    int nnum[10];
    bool flag[10];

    int A(int m,int n){
        if(n>m)return 0;
        if(m==0)return 0;
        return frac[m]/frac[m-n];
    }

    int sum(int total,int curr){
        if(curr<0)return 1;
        int result=0;
        int n=nnum[curr];
        for(int i=n-1;i>=0;i--){
            if(total==curr+1&&i==0){
                for(int j=curr;j>0;j--){
                    result+=(A(10,j)-A(9,j-1));
                }

            }
            else if(!flag[i])result += A(10-total+curr,curr);
        }
        if(!flag[n]){
            flag[n]=true;
            result+=sum(total,curr-1);
        }

        return result;
    }
    int countSpecialNumbers(int n) {
        frac[0]=frac[1]=1;
        for(int i=2;i<11;i++)frac[i]=frac[i-1]*i;
        memset(nnum,0,sizeof(nnum));
        memset(flag,0,sizeof(flag));

        int N=n;
        int d=0;
        while(N){
            nnum[d++]=N%10;
            N/=10;
        }

        return sum(d,d-1);

    }
};

class Solution {
  private static final List<Long> vals = new ArrayList<>();
  private static int len = 0;
  static {
    len = 10;
    for (int i = 1; i <= len; i++) dfs(0L, 0, i, 2000000000, 0);
  }
  public int countSpecialNumbers(int n) {
    int idx = Collections.binarySearch(vals, 0L + n);
    if (idx < 0) return -(idx + 1);
    return idx + 1;
  }
  
  private static void dfs(long val, int idx, int len, int max, int mask) {
    if (idx == len) {
      if (val <= max && val > 0) {
        vals.add(val);
      }
      return;
    }
    
    // choose an unused digit
    for (int i = 0; i <= 9; i++) if ((mask & (1 << i)) == 0) {
      if (val == 0 && i == 0) continue;
      dfs(val * 10 + i, idx + 1, len, max, mask ^ (1 << i));
    }
  }
    
  private static int computeLen(int n) {
    int res = 0;
    while (n > 0) {
      n /= 10;
      res++;
    }
    return res;
  }
}

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        
        nums = [int(x) for x in str(n)]
        memo = {}
        
        def digitDP(pos, flag, lead, mask):
            if pos == len(nums):
                return 1
            
            key = (pos, flag, lead, mask)
            if key in memo:
                return memo[key]
            
            if flag == 0:
                limit = nums[pos]
            else:
                limit = 9
            res = 0
            for i in range(limit + 1):
                newFlag = flag or (i < limit)
                newLead = lead or (i > 0)
                if newLead: # no leading zero
                    if not mask & (1<<i): # if the digit is not used
                        res += digitDP(pos+1, newFlag, newLead, mask|(1<<i))
                else:
                    res += digitDP(pos+1, newFlag, newLead, mask)

            memo[key] = res
            return res
        
        return digitDP(0, 0, 0, 0) - 1

Happy Learning – If you require any further information, feel free to contact me.