Skip to main content
Talentd

Count Special Integers - Solution & Explanation

HardMathDynamic Programming24 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer n, count how many numbers in the range [1, n] have all digits distinct. Any number containing repeated digits (like 11 or 232) is excluded. The challenge is efficiently counting valid numbers without checking every integer up to n.

Approach 1: Backtracking Enumeration (Time: O(10!), Space: O(10))

This approach generates numbers with unique digits using backtracking. Start from digits 1-9, track used digits with a boolean array, and recursively append unused digits. Stop exploring once the constructed number exceeds n. Each recursive step tries digits 0-9 that haven't been used, ensuring the number maintains the distinct-digit property.

The key insight is pruning early: if the current number is already greater than n, the branch stops immediately. This avoids scanning every number up to n. The search tree is bounded by permutations of digits (at most 10 levels). This method clearly shows the structure of valid numbers and is easy to reason about, but it becomes less elegant compared to direct counting.

Approach 2: Counting by Digit Positions (Digit Combinatorics) (Time: O(d * 10), Space: O(1))

The optimal approach counts valid numbers digit by digit instead of generating them. Let d be the number of digits in n. First count all valid numbers with fewer digits using permutation formulas. For example, for length k, the first digit has 9 choices (1-9), and remaining digits use permutations of unused digits.

Then process numbers with the same length as n. Iterate through each digit from left to right. For each position, count how many smaller digits can be placed there that haven't been used before, and multiply by the permutations of remaining digits. Maintain a set of used digits; if a digit repeats, the process stops because further prefixes would contain duplicates.

This method is essentially a combinatorics-driven form of digit DP. Instead of exploring every number, it directly counts how many valid permutations fit under the prefix constraint of n. The runtime depends only on the number of digits in n, making it extremely efficient.

Key concepts include permutation counting from math, prefix constraints from dynamic programming, and digit-level enumeration techniques commonly used in digit DP problems.

Recommended for interviews: The digit-position counting approach is what most interviewers expect. It shows strong understanding of combinatorics and prefix constraints. The backtracking solution demonstrates the idea of generating unique-digit numbers, but the counting method proves you can convert enumeration into a mathematical count with optimal complexity.

Approach 1: Backtracking Approach

This approach involves using backtracking to explore all possible numbers with distinct digits. For each number, check the digits and ensure they are unique.

It is efficient for smaller n but still performs well for given constraints due to digit limitations.

Here, the countSpecialNumbers function calculates the number of special integers less than or equal to n. It uses combinations of the digits, ensures uniqueness by checking seen digits, and adds permutations for counting possible numbers.

Code

PythonC++JavaC

Python

C++

Java

C

Complexity

Time Complexity: O(d!) where d is the number of digits in n; it effectively handles permutations.

Space Complexity: O(d) for the recursion stack and seen digits storage.

Try this approach in the editor →

Approach 2: Counting by Digit Positions

This approach counts special numbers by evaluating the number at each digit position in terms of possible values. Precalculate special numbers for known lengths and multiply permutations iterating over valid digits.

The JavaScript implementation uses factorial function for permutations and Set for tracking already used digits to ensure the specialness of the number.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(d!) as it assesses permutations.

Space Complexity: O(d) for the Set tracking and string manipulation.

Try this approach in the editor →

Approach 3: State Compression + Digit DP

This problem essentially asks for the number of numbers in the given range [l, ..r] that satisfy certain conditions. The conditions are related to the composition of the numbers rather than their size, so we can use the concept of Digit DP to solve it. In Digit DP, the size of the number has little impact on the complexity.

For the range [l, ..r] problem, we generally convert it to the problem of [1, ..r] and then subtract the result of [1, ..l - 1], i.e.:

$ ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i

However, for this problem, we only need to find the value for the range [1, ..n].

Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.

Based on the problem information, we design a function dfs(i, mask, lead, limit), where:

  • The digit i represents the current position being searched, starting from the highest digit, i.e., i = 0 represents the highest digit.
  • The digit mask represents the current state of the number, i.e., the j-th bit of mask being 1 indicates that the digit j has been used.
  • The boolean lead indicates whether the current number only contains leading 0s.
  • The boolean limit indicates whether the current number is restricted by the upper bound.

The function executes as follows:

If i exceeds the length of the number n, it means the search is over. If lead is true, it means the current number only contains leading 0s, so return 0. Otherwise, return 1.

If limit is false and lead is false and the state of mask has been memoized, directly return the memoized result.

Otherwise, we calculate the current upper bound up. If limit is true, up is the i-th digit of the current number. Otherwise, up = 9.

Then we iterate over [0, up]. For each digit j, if the j-th bit of mask is 1, it means the digit j has been used, so we skip it. Otherwise, if lead is true and j = 0, it means the current number only contains leading 0s, so we recursively search the next digit. Otherwise, we recursively search the next digit and update the state of mask.

Finally, if limit is false and lead is false, memoize the current state.

Return the final answer.

The time complexity is O(m times 2^D times D), and the space complexity is O(m times 2^D). Here, m is the length of the number n, and D = 10$.

Similar Problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(d!) where d is the number of digits in n; it effectively handles permutations.

Space Complexity: O(d) for the recursion stack and seen digits storage.

Counting by Digit Positions

Time Complexity: O(d!) as it assesses permutations.

Space Complexity: O(d) for the Set tracking and string manipulation.

State Compression + Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(10!) worst caseO(10)Useful for understanding how unique-digit numbers are formed or when demonstrating recursive generation techniques
Counting by Digit Positions (Combinatorics / Digit DP)O(d * 10)O(1)Best for interviews and large inputs; avoids enumeration by counting valid permutations under prefix constraints

Video Solution

2376. Count Special Integers | Leetcode Weekly Contest 306 | LeetCode 2376 • Bro Coders • 3,604 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Special Integers easy or hard?
Count Special Integers is labeled Hard because it requires recognizing a digit DP or combinatorics counting pattern. Brute force approaches are straightforward but inefficient. The difficulty lies in converting the problem into counting permutations of unused digits under prefix constraints.
Count Special Integers Python or Java solution
Python and Java implementations typically follow the digit counting strategy: compute permutations for shorter lengths, then iterate through digits of n while tracking used digits. If a duplicate digit appears, the loop stops early. FleetCode provides full implementations in Python, Java, C++, C#, and JavaScript.
How to solve Count Special Integers in O(log n)?
Treat the number digit by digit. First count all valid numbers with fewer digits using permutations. Then iterate through each digit of n and count how many smaller unused digits can appear at that position, multiplying by permutations of remaining digits. Stop when a repeated digit appears. This digit-based counting runs proportional to the number of digits, which is O(log n).
What is the best approach for Count Special Integers?
The most efficient approach uses digit position counting with combinatorics, often described as a digit DP style solution. It counts valid numbers by analyzing each digit of n and calculating how many permutations of unused digits fit under the prefix constraint. This runs in O(d * 10) time where d is the number of digits in n, which is much faster than generating numbers directly.
What data structure is used in Count Special Integers?
Most solutions use a small boolean array or set to track which digits have already been used while processing the digits of n. The algorithm also relies on permutation calculations from combinatorics rather than heavy data structures.
What is the time complexity of Count Special Integers?
The optimal combinatorics-based solution runs in O(d * 10) time where d is the number of digits in n. Since d is at most 10 for typical integer constraints, the algorithm is effectively constant time. Space complexity is O(1) because only a small set or boolean array is used to track used digits.
Is Count Special Integers asked at Google, Amazon, or Meta?
Digit DP and combinatorics counting problems similar to Count Special Integers appear in interviews at companies like Google, Amazon, and Meta. Interviewers often test the ability to convert brute-force enumeration into a counting problem using permutations and prefix constraints.

Ready to solve this problem?

Practice Count Special Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Numbers with Unique Digits

Next

K-th Smallest in Lexicographical Order