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

Numbers With Repeated Digits

Number: 1057

Difficulty: Hard

Paid? No

Companies: J.P. Morgan, IBM, Google

Problem Description

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Key Insights

  • Instead of directly counting numbers with repeated digits, count the numbers with all unique digits and subtract from n.
  • Use combinatorial methods to calculate the number of numbers with distinct digits for lengths smaller than the length of n.
  • Count numbers with the same number of digits as n using digit-by-digit analysis while avoiding repetitions.
  • The limited set of digits (0-9) allows the use of permutation formulas without incurring high computational costs.

Space and Time Complexity

Time Complexity: O(10) per operation as the maximum digit length is 10. Space Complexity: O(1)

Solution

The approach involves counting numbers with unique digits up to n and then subtracting that count from n to find numbers that have at least one repeated digit. First, count numbers with fewer digits than n using permutation formulas (9 * P(9, k-1) for each valid k). Then, for numbers having the same digit length as n, iterate through each digit and count the valid choices for that digit that have not already been used, using permutations for the remaining positions. The trick is careful handling of repetitions and the restriction on zero for the leading digit.

Code Solutions

def numDupDigitsAtMostN(n: int) -> int:
    # Helper function to calculate permutation: P(m, k) = m * (m-1) * ... * (m-k+1)
    def permutation(m: int, k: int) -> int:
        result = 1
        for i in range(k):
            result *= (m - i)
        return result

    s = str(n)
    num_digits = len(s)
    unique_count = 0

    # Count numbers with digits less than num_digits
    for i in range(1, num_digits):
        unique_count += 9 * permutation(9, i - 1)

    seen = set()
    # Count numbers with the same number of digits
    for i in range(num_digits):
        digit = int(s[i])
        for d in range(0 if i > 0 else 1, digit):
            if d in seen:
                continue
            remaining = num_digits - i - 1
            unique_count += permutation(10 - i - 1, remaining)
        if digit in seen:
            break
        seen.add(digit)

    return n - unique_count

# Example usages:
print(numDupDigitsAtMostN(20))   # Expected output: 1
print(numDupDigitsAtMostN(100))  # Expected output: 10
← Back to All Questions