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 At Most N Given Digit Set

Number: 938

Difficulty: Hard

Paid? No

Companies: TikTok, Amazon

Problem Description

Given a sorted array of unique digits (represented as strings) that can be reused arbitrarily, the task is to count how many positive integers can be formed that are less than or equal to a given integer n. The numbers are formed by concatenating the digits from the given array.

Key Insights

  • Count numbers with a digit-length strictly less than the length of n; every combination is valid.
  • Handle numbers with the same digit-length as n digit by digit.
  • For each digit in the same-length number, consider:
    • The count of available digits less than the corresponding digit in n multiplied by the number of completions with any digits thereafter.
    • If the digit equal to the current digit in n exists, continue to the next digit.
  • If a chosen digit does not equal the current digit in n and is not less than it, break the loop.
  • This approach is similar to digit dynamic programming but done greedily with careful counting.

Space and Time Complexity

Time Complexity: O(m * k) where m is the number of digits in n and k is the number of given digits. Space Complexity: O(1) or O(m) if considering the string representation conversion space.

Solution

The solution counts valid numbers in two parts:

  1. Count numbers with digit-length strictly smaller than that of n. For each d-digit number where d < len(n), the count is (number of given digits)^d.
  2. Count numbers with the same digit-length as n. Process each digit from left to right; for the current digit, count digits in the given array that are less than the corresponding digit in n and multiply by the number of completions possible for the remaining positions. If a matching digit is found, continue; if not, break. Finally, if we completed all digits matching, include the number n itself.

Key data structures include simple variables for counting and arithmetic operations; no elaborate structure is required. The algorithm leverages greedy decisions at each digit position.

Code Solutions

# Python Solution
def atMostNGivenDigitSet(digits, n):
    # Convert n to string for easy digit comparison
    s = str(n)
    n_len = len(s)
    k = len(digits)
    count = 0

    # Count numbers with length less than n
    for i in range(1, n_len):
        count += k ** i

    # Process numbers with length equal to n
    for i, ch in enumerate(s):
        # Count valid digits less than current digit ch in n
        smaller_count = 0
        for d in digits:
            if d < ch:
                smaller_count += 1
            else:
                break  # since digits is sorted, no further digit is smaller

        # Options for the current digit position multiplied by choices for remaining positions
        count += smaller_count * (k ** (n_len - i - 1))

        # If the current digit ch is not in digits, no need to continue further
        if ch not in digits:
            return count  # early termination

    # If the loop completes, n itself can be formed using digits
    return count + 1

# Example usage:
#print(atMostNGivenDigitSet(["1", "3", "5", "7"], 100))
← Back to All Questions