Count Special Integers - Practice Coding Problems

Count Special Integers - 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].

A special integer has no repeated digits. For example, 123 is special, but 112 is not special because digit 1 appears twice.

Input & Output

Example 1 — Small Range

$ Input: n = 20

› Output: 18

💡 Note: Special integers from 1 to 20: 1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20. We exclude 11 because digit 1 repeats. All other numbers have distinct digits.

Example 2 — Single Digit

$ Input: n = 5

› Output: 5

💡 Note: All numbers from 1 to 5 have distinct digits: 1,2,3,4,5. Each single-digit number is automatically special.

Example 3 — Edge Case

$ Input: n = 100

› Output: 90

💡 Note: Includes all 1-digit (9) and 2-digit numbers with distinct digits (9×9=81), but excludes 100 because it has repeated 0s. Total: 9 + 81 = 90.

Constraints

1 ≤ n ≤ 2 × 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given range [1, n], need to count special integers

Special Check

A number is special if no digit repeats

Count Result

Return total count of special integers

Key Takeaway

🎯 Key Insight: Use mathematical patterns or digit DP to count efficiently instead of checking each number individually

Asked in

G Google 15 a Amazon 8 M Microsoft 6

The key insight is that most numbers follow predictable patterns for distinct digits, so we can use mathematical formulas or digit DP instead of checking each number individually. Best approach is Digit DP with memoization for O(d × 2¹⁰) time complexity where d is the number of digits in n.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Combinatorics	O(d²)	O(1)	Calculate using permutation formulas for different digit lengths
Brute Force	O(n × d)	O(d)	Check each number from 1 to n for distinct digits
Digit DP with Memoization	O(d × 2^10 × 2 × 2)	O(d × 2^10 × 2 × 2)	Build numbers digit by digit using dynamic programming

Mathematical Combinatorics — Algorithm Steps

Count 1-digit numbers (1-9): 9 numbers
Count 2-digit numbers: 9 × 9 (first digit 1-9, second from remaining)
Count d-digit numbers: 9 × P(9, d-1)
Handle the final partial group up to n

Visualization

Tap to expand

Step-by-Step Walkthrough

1-digit

Count 1,2,3,4,5,6,7,8,9 = 9 numbers

2-digit

9 × 9 = 81 numbers (first digit 1-9, second from remaining)

3+ digits

Use permutations: 9 × P(9,k-1) for k-digit numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char s[15];
int len;

int countValid(int pos, int mask, int tight, int started) {
    if (pos == len) {
        return started;
    }
    
    int limit = tight ? (s[pos] - '0') : 9;
    int count = 0;
    
    for (int digit = 0; digit <= limit; digit++) {
        if (started && (mask & (1 << digit))) {
            continue;
        }
        
        int newMask = mask;
        int newStarted = started;
        
        if (digit > 0 || started) {
            newMask |= (1 << digit);
            newStarted = 1;
        }
        
        int newTight = tight && (digit == limit);
        count += countValid(pos + 1, newMask, newTight, newStarted);
    }
    
    return count;
}

int solution(int n) {
    if (n == 0) return 1;
    
    sprintf(s, "%d", n);
    len = strlen(s);
    int result = 0;
    
    // Count numbers with fewer digits
    if (len > 1) {
        result += 9; // 1-digit numbers
    }
    
    // 2-digit, 3-digit, ... up to (len-1)-digit numbers
    for (int digits = 2; digits < len; digits++) {
        int count = 9; // First digit choices
        int remaining = 9;
        for (int i = 1; i < digits; i++) {
            count *= remaining;
            remaining--;
        }
        result += count;
    }
    
    // Count numbers with same number of digits as n
    result += countValid(0, 0, 1, 0);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d²)

d iterations for digit lengths, each doing O(d) permutation calculation where d = log₁₀(n)

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for calculations

✓ Linear Space

23.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Combinatorics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler