304 North Cardinal St.
Dorchester Center, MA 02124

# 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;

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
}

// DP state

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;

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;

ans += gogo(s, 0, pos + 1, newMask);
}
}
}
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][(1 << 11) - 1];
for(int i = 0; i <= len; i++){
Arrays.fill(cache[i], -1);
Arrays.fill(cache[i], -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;

int count = 0;
int limit = tight == 1 ? digits[place] : 9;
for(int i = 0; i <= limit; i++) {
// 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));
}

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:
return res

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