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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Special Integers

Difficulty: Hard

Problem Description

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].

Key Insights

  • A number is special if no digit appears more than once.
  • We can count special numbers by considering the digits and their arrangements.
  • The problem can be approached by breaking it down into ranges based on the number of digits.
  • For numbers with fewer digits than n, all combinations are special.
  • For numbers with the same number of digits as n, we need to be careful to not exceed n while counting.

Space and Time Complexity

Time Complexity: O(1) - The number of calculations is constant with respect to the size of n. Space Complexity: O(1) - We use a fixed amount of space regardless of the input size.

Solution

To solve the problem, we will use a combinatorial approach to count the special integers. The idea is to first calculate how many special integers can be formed with fewer digits than n, and then consider numbers that have the same number of digits as n. We will keep track of the digits used to ensure they remain distinct.

  1. Count all special integers with lengths less than the number of digits in n.
  2. For the numbers with the same number of digits as n, check each digit position and count valid configurations that do not exceed n while ensuring uniqueness of digits.

The algorithm will effectively utilize combinatorial calculations to determine the number of valid arrangements.

Code Solutions

def countSpecialNumbers(n: int) -> int:
    str_n = str(n)
    length = len(str_n)
    count = 0
    
    # Count special numbers with fewer digits than n
    for i in range(1, length):
        count += 9 * permutation(9, i - 1)
    
    # Count special numbers with the same number of digits as n
    used = set()
    for i in range(length):
        limit = int(str_n[i])
        for digit in range(0 if i > 0 else 1, limit):
            if digit not in used:
                count += permutation(9 - i, length - i - 1)
        if limit in used:
            break
        used.add(limit)
    
    return count + 1  # Include n itself if it is special

def permutation(n: int, k: int) -> int:
    if k > n:
        return 0
    result = 1
    for i in range(k):
        result *= n - i
    return result
← Back to All Questions