Count Special Integers LeetCode Solution

Problem – Count Special Integers LeetCode Solution

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

Count Special Integers LeetCode Solution in C++

    
    int dp[11][2][1024];
    
    int gogo(string &s, int tight = 1, int pos = 0, int mask = 0) {
        // Base case
        if(pos == s.size()) {
            // Mask = 0, represents 00000...0 which should not be counted
            return mask != 0;
        }
        
        // DP state
        if(dp[pos][tight][mask] != -1)
            return dp[pos][tight][mask];
        
        int ans = 0;

        if(tight == 1) {
            
            // Limit the current digit
            for(int i = 0; i <= s[pos] - '0'; i++) {
                
                // Check if digit repeated, ie, present in the mask
                if(mask & (1 << i)) continue;
                

                int newMask = (mask == 0 && i == 0 ? mask : (mask | (1 << i)));
                
                if(i == s[pos] - '0') {
                    // Tight case
                    ans += gogo(s, 1, pos + 1, newMask);
                } else {
                    ans += gogo(s, 0, pos + 1, newMask);
                }
            }
        } else {
            for(int i = 0; i <= 9; i++) {
                
                // Check if digit repeated, ie, present in the mask
                if(mask & (1 << i)) continue;
                
                int newMask = (mask == 0 && i == 0 ? mask : (mask | (1 << i)));
                ans += gogo(s, 0, pos + 1, newMask);
            }
        }
        return dp[pos][tight][mask] = ans;
    }
public:
    int countSpecialNumbers(int n) {
        string s = to_string(n);
        memset(dp, -1, sizeof(dp));
        return gogo(s);
    }
};

Count Special Integers LeetCode Solution in Java

class Solution {
    int[][][] cache;
    int[] digits;
    public int countSpecialNumbers(int n) {
        int len = findLen(n); // finding digit length of n. For 135 -> 3, for 1345 -> 4.
        cache = new int[len + 1][2][(1 << 11) - 1];
        for(int i = 0; i <= len; i++){
            Arrays.fill(cache[i][0], -1);
            Arrays.fill(cache[i][1], -1);
        }
        
        digits = new int[len + 1]; // store the digits of num. For 135 -> {5, 3, 1}, for 1354 -> {4, 5, 3, 1}
        int place = 1;
        while(n > 0) {
            digits[place++] = n % 10;
            n /= 10;
        }
        
		// minus 1 to remove the '0' we counted during solve.
        return solve(len, 1, 0) - 1;
    }
    
    private int solve(int place, int tight, int mask) {
        if(place == 0) return 1;
        if(cache[place][tight][mask] != -1) return cache[place][tight][mask];
        
        int count = 0;
        int limit = tight == 1 ? digits[place] : 9;
        for(int i = 0; i <= limit; i++) {
            if(isSet(mask, i)) continue;
			// if i == limit and tight = 1(digit is restricted) -> new_tight = 1
			// mask == 0 && i == 0 ? mask : setBit(mask, i) -> don't set count '0'  as used digit if this is the first digit. 
			//for eg: in 001304, we don't count first 2 '0' as used. But we count the 3rd '0' as used.
            count += solve(place - 1, i == limit && tight == 1 ? 1 : 0, mask == 0 && i == 0 ? mask : setBit(mask, i));
        }
        
        cache[place][tight][mask] = count;
        return count;
    }
    
    private boolean isSet(int mask, int i) {
        return (mask & (1 << i)) != 0;
    }
    
    private int setBit(int mask, int i) {
        return (mask | (1 << i));
    }
    
    private int findLen(int n) {
        int len = 0;
        while(n > 0) {
            len++;
            n /= 10;
        }
        return len;
    }
}

Count Special Integers LeetCode Solution in Python

from functools import reduce
class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        def f(n):
            if n == 0: return 0
            # 1<= special numbers < 10^n
            res = temp = 9
            for i in range(n-1):
                temp *= (9-i)
                res += temp 
            return res
        
        nums = list(map(int,str(n)))
        n = len(nums)
        res = f(n-1)
        seen = set()
        
        for i, num in enumerate(nums):
            # fix the i-th digit: ___ (0) ... <= special numbers <= ___ (num-1) ... <- here num is the real i-th digit in nums, ___ means the idential digits, choices of the i-th digit:
            intials = len([j for j in range(max(1-i,0),num) if j not in seen])
            # candiates for ... tail part
            k = 9 - len(seen)
            res += intials*reduce(lambda x,y:x*y, range(k,k-(n-1-i),-1),1)
            if num in seen:
                # no numbers can start with nums[:i+1] now
                return res
            seen.add(num)
            
        return res + 1

Count Special Integers LeetCode Solution Review:

In our experience, we suggest you solve this Count Special Integers LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Count Special Integers LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Count Special Integers LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions