Count Special Integers

Hard

#2163Time: O((log10(n))^2). The number of digits `L` is O(log10(n)). The first loop runs `L` times, and the second loop runs `L` times with an inner loop of constant size (10). The `permutations` function also takes O(L) time. This results in a very fast solution.Space: O(log10(n)). We use a string to store `n` and a boolean array of size 10. The space is dominated by the string representation of `n`.

Patterns

Math Dynamic Programming

Prompt

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 * 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A much more efficient method is to use digit dynamic programming, which builds the count based on the digits of n. Instead of checking every number, we can count the number of valid special integers mathematically. We can count the special integers with fewer digits than n and then count the special integers with the same number of digits as n but are less than or equal to n.

Algorithm

The problem is to count special numbers up to n. This can be solved using digit dynamic programming and combinatorics. Let S be the string representation of n and L be its length.

The count is divided into two parts:

Count special numbers with fewer digits than n:
- Iterate for each length d from 1 to L-1.
- For a d-digit number, the first digit has 9 choices (1-9). The remaining d-1 digits are a permutation of d-1 digits chosen from the 9 remaining available digits (0-9 excluding the first digit).
- The count for length d is 9 * P(9, d-1), where P(m, k) is the number of k-permutations of m.
- Sum these counts for all d < L.
Count special numbers with the same number of digits as n and are less than or equal to n:
- Iterate through the digits of n from left to right (index i from 0 to L-1).
- Maintain a set of digits seen in the prefix.
- At each position i, consider placing a digit d that is smaller than the digit n[i].
- For each such valid d (not 0 for the first position and not in seen), the remaining L-1-i positions can be filled in P(10 - (i+1), L-1-i) ways. Add this to the total count.
- After checking smaller digits, check the digit n[i] itself. If n[i] is already in seen, it means n and any other number with this prefix is not special. We must stop and return the current count.
- If n[i] is not in seen, add it to seen and proceed to the next position i+1.
Final check for n:
- If the loop completes, it means n itself is a special number. Increment the final count by 1.

Walkthrough

Let's illustrate with n = 135. The string is S = "135" and length L = 3.

Part 1: Count special numbers with length < 3

1-digit numbers: 9 (1-9).
2-digit numbers: The first digit has 9 choices (1-9). The second has 9 choices (0-9, excluding the first). Total: 9 * 9 = 81.
Total for length < 3: 9 + 81 = 90.

Part 2: Count 3-digit special numbers <= 135

We iterate through S = "135".
Position 0 (hundreds): S[0] = '1'. We can't place a smaller digit (since it would have to be 0, which is not allowed as the first digit). So we must place '1'. Mark '1' as seen.
Position 1 (tens): S[1] = '3'. We can place digits smaller than 3.
- Try d = 0: '0' is not seen. We form 10_. The last digit has 8 choices (0-9, excluding 1 and 0). Add 8 to count.
- Try d = 2: '2' is not seen. We form 12_. The last digit has 8 choices. Add 8 to count.
- Now, we must place '3'. Mark '3' as seen.
Position 2 (ones): S[2] = '5'. We can place digits smaller than 5.
- Try d = 0, 2, 4 (1 and 3 are seen). For each, we form 130, 132, 134. These are 3 numbers. Add 3 to count.
The loop finishes. Since 135 itself has distinct digits, we add 1 for it.
Total for 3-digit numbers: 8 + 8 + 3 + 1 = 20.

Grand Total: 90 + 20 = 110.

Here is the code for this approach:

1class Solution {2    public int countSpecialNumbers(int n) {3        String s = String.valueOf(n);4        int L = s.length();5        int res = 0;6 7        // Count special numbers with length < L8        for (int d = 1; d < L; d++) {9            res += 9 * permutations(9, d - 1);10        }11 12        // Count special numbers with length L and <= n13        boolean[] seen = new boolean[10];14        for (int i = 0; i < L; i++) {15            int digit = s.charAt(i) - '0';16            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {17                if (!seen[d]) {18                    res += permutations(10 - (i + 1), L - 1 - i);19                }20            }21            if (seen[digit]) {22                return res; // Duplicate digit found in n's prefix23            }24            seen[digit] = true;25        }26 27        // If we reach here, n itself is a special number28        res++;29        return res;30    }31 32    // Calculates P(m, n) = m! / (m-n)!33    private int permutations(int m, int n) {34        if (n > m) return 0;35        int res = 1;36        for (int i = 0; i < n; i++) {37            res *= (m - i);38        }39        return res;40    }41}

Complexity

Time

O((log10(n))^2). The number of digits `L` is O(log10(n)). The first loop runs `L` times, and the second loop runs `L` times with an inner loop of constant size (10). The `permutations` function also takes O(L) time. This results in a very fast solution.

Space

O(log10(n)). We use a string to store `n` and a boolean array of size 10. The space is dominated by the string representation of `n`.

Trade-offs

Pros

Extremely efficient and fast, easily passing the given constraints.
The time complexity depends only on the number of digits in n, not its magnitude.

Cons

The logic is more complex than the brute-force approach.
Requires careful handling of edge cases, like the first digit not being zero and tracking used digits.

The most straightforward approach is to simulate the process directly. We can iterate through every integer from 1 up to n and, for each integer, check if it meets the criteria of being "special" (i.e., all its digits are distinct). We maintain a count of such numbers found.

Algorithm

Initialize a counter special_count to 0.
Iterate through each integer i from 1 to n.
For each integer i, check if it is a "special integer".
- To check if i is special, we can convert it to a sequence of its digits.
- Use a frequency map or a set to keep track of the digits encountered.
- Iterate through the digits. If a digit is already in our set, the number is not special. Otherwise, add the digit to the set.
- If we process all digits without finding a duplicate, the number is special.
If i is a special integer, increment special_count.
After the loop finishes, return special_count.

Walkthrough

This method involves a simple loop from 1 to n. Inside the loop, a helper function, let's call it isSpecial(num), determines if a number has unique digits.

The isSpecial function can work by repeatedly taking the number modulo 10 to get the last digit and then dividing by 10 to process the next digit. A boolean array or a hash set can be used to keep track of the digits seen so far. If a digit is encountered more than once, the number is not special.

Here is a code implementation of this approach:

1class Solution {2    // Helper function to check if a number has distinct digits3    private boolean isSpecial(int num) {4        boolean[] seen = new boolean[10];5        while (num > 0) {6            int digit = num % 10;7            if (seen[digit]) {8                return false;9            }10            seen[digit] = true;11            num /= 10;12        }13        return true;14    }15 16    public int countSpecialNumbers(int n) {17        int count = 0;18        for (int i = 1; i <= n; i++) {19            if (isSpecial(i)) {20                count++;21            }22        }23        return count;24    }25}

Complexity

Time

O(n * log10(n)). We iterate `n` times. For each number `i`, the `isSpecial` check takes O(log10(i)) time, as the number of digits is logarithmic with respect to the number's value.

Space

O(log10(n)) or O(1). The `isSpecial` function uses a boolean array of constant size 10. The space used for the number's digits is proportional to log10(n), which is small.

Trade-offs

Pros

Very easy to understand and implement.
It's a good starting point for verifying the logic with small test cases.

Cons

The time complexity is directly proportional to n, which is too slow for the given constraints (n up to 2 * 10^9).
This approach will result in a Time Limit Exceeded (TLE) error on most platforms.

Solutions

Solution

1class Solution { public int countSpecialNumbers ( int n ) { List < Integer > digits = new ArrayList <>(); while ( n != 0 ) { digits . add ( n % 10 ); n /= 10 ; } int m = digits . size (); int ans = 0 ; for ( int i = 1 ; i < m ; ++ i ) { ans += 9 * A ( 9 , i - 1 ); } boolean [] vis = new boolean [ 10 ]; for ( int i = m - 1 ; i >= 0 ; -- i ) { int v = digits . get ( i ); for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) { if ( vis [ j ]) { continue ; } ans += A ( 10 - ( m - i ), i ); } if ( vis [ v ]) { break ; } vis [ v ] = true ; if ( i == 0 ) { ++ ans ; } } return ans ; } private int A ( int m , int n ) { return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 ); } }

1class Solution { public: int countSpecialNumbers ( int n ) { int ans = 0 ; vector < int > digits ; while ( n ) { digits . push_back ( n % 10 ); n /= 10 ; } int m = digits . size (); vector < bool > vis ( 10 ); for ( int i = 1 ; i < m ; ++ i ) { ans += 9 * A ( 9 , i - 1 ); } for ( int i = m - 1 ; ~ i ; -- i ) { int v = digits [ i ]; for ( int j = i == m - 1 ? 1 : 0 ; j < v ; ++ j ) { if ( ! vis [ j ]) { ans += A ( 10 - ( m - i ), i ); } } if ( vis [ v ]) { break ; } vis [ v ] = true ; if ( i == 0 ) { ++ ans ; } } return ans ; } int A ( int m , int n ) { return n == 0 ? 1 : A ( m , n - 1 ) * ( m - n + 1 ); } };

1class Solution : def countSpecialNumbers ( self , n : int ) -> int : def A ( m , n ): return 1 if n == 0 else A ( m , n - 1 ) * ( m - n + 1 ) vis = [ False ] * 10 ans = 0 digits = [ int ( c ) for c in str ( n )[:: - 1 ]] m = len ( digits ) for i in range ( 1 , m ): ans += 9 * A ( 9 , i - 1 ) for i in range ( m - 1 , - 1 , - 1 ): v = digits [ i ] j = 1 if i == m - 1 else 0 while j < v : if not vis [ j ]: ans += A ( 10 - ( m - i ), i ) j += 1 if vis [ v ]: break vis [ v ] = True if i == 0 : ans += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem