We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Special Integers

Number: 2457

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a positive integer n, count how many numbers in the range [1, n] are "special" (i.e. all digits within the number are distinct).

Key Insights

  • The problem is effectively about counting numbers with distinct digits.
  • For numbers with fewer digits than n, we can employ combinatorial counting.
  • For numbers with the same number of digits as n, a digit dynamic programming (DP) approach is used to count valid numbers without over-counting.
  • A state in the DP typically tracks the current position, whether we are bound by the prefix of n (tight condition), and which digits have already been used (using a bitmask).
  • Since n ≤ 2×10^9, the maximum digit length is 10, which helps keep the DP state space manageable.

Space and Time Complexity

Time Complexity: O(10 * 2^10) (since the state space is bounded by the positions, used digits with a bitmask, and the tight constraint). Space Complexity: O(10 * 2^10) due to the memoization cache, which is effectively constant space with respect to n.

Solution

We solve the problem in two parts:

  1. Count numbers with distinct digits that have fewer digits than n using combinatorial methods.
  2. Count numbers with the same number of digits as n using a digit DP approach.

For the DP part:

  • Use a recursive function that processes one digit at a time.
  • Keep track of whether the current prefix matches the prefix of n (tight bound).
  • Use a bitmask to record which digits have been used so far.
  • For each digit, if the tight condition holds, restrict the available digits to those not greater than the corresponding digit in n.
  • Handle the case of leading zeros carefully (they are not allowed in normal non-zero numbers).

The trickiest part is managing the tight constraint and ensuring that once the current number becomes smaller than that of n (i.e., relaxed), we can freely choose any unused digit for subsequent positions using combinatorial counting.

Code Solutions

def countSpecialNumbers(n: int) -> int:
    s = str(n)
    L = len(s)
    
    # Count numbers with distinct digits for numbers with length < L
    def permutation(m, k):
        # Computes P(m, k) = m * (m-1) * ... * (m-k+1)
        res = 1
        for i in range(k):
            res *= (m - i)
        return res
    
    count = 0
    # For numbers with digits = 1 to L-1
    for l in range(1, L):
        # For l-digit numbers, the first digit can be 1-9 and rest must be distinct from first.
        count += 9 * permutation(9, l - 1)
    
    # DP for numbers with L digits using recursion with memoization
    # dp(pos, used_mask, tight) returns count of valid numbers from pos onward
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(pos, used_mask, tight):
        if pos == L:
            return 1  # valid complete number
        total = 0
        # Determine the upper bound for the current digit
        upper = int(s[pos]) if tight else 9
        for dig in range(0, upper + 1):
            # For first digit, cannot choose 0
            if pos == 0 and dig == 0:
                continue
            # Skip if this digit has already been used
            if used_mask & (1 << dig):
                continue
            next_tight = tight and (dig == upper)
            total += dp(pos + 1, used_mask | (1 << dig), next_tight)
        return total
    
    # Count for numbers with exactly L digits.
    count += dp(0, 0, True)
    return count

# Example usage:
print(countSpecialNumbers(20))   # Expected 19
print(countSpecialNumbers(135))  # Expected 110
← Back to All Questions