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

Numbers At Most N Given Digit Set

Difficulty: Hard

Problem Description

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Key Insights

  • The digits can be reused to form numbers of varying lengths.
  • We need to consider numbers with lengths from 1 up to the number of digits in n.
  • Count all valid numbers of lengths less than the number of digits in n.
  • For numbers with the same length as n, we need to compare digits positionally to ensure they remain less than or equal to n.

Space and Time Complexity

Time Complexity: O(K + M) where K is the number of digits and M is the number of digits in n. Space Complexity: O(1) since we are only using a constant amount of space.

Solution

The solution involves counting the numbers that can be formed with the given digits. We first count all the numbers that can be formed with fewer digits than n. For numbers with the same number of digits as n, we will construct these numbers digit by digit, ensuring that they remain less than or equal to n.

  1. Count numbers with lengths < len(n).
  2. For numbers with length equal to len(n), iterate through each digit of n and count how many valid numbers can be formed.

We will utilize combinatorial counting for numbers with fewer digits and positional comparisons for numbers with the same length.

Code Solutions

def atMostNGivenDigitSet(digits, n):
    str_n = str(n)
    len_n = len(str_n)
    len_digits = len(digits)
    
    # Count numbers with fewer digits than n
    count = 0
    for i in range(1, len_n):
        count += len_digits ** i
    
    # Count numbers with the same number of digits as n
    for i in range(len_n):
        has_same_prefix = False
        for d in digits:
            if d < str_n[i]:
                count += len_digits ** (len_n - i - 1)
            elif d == str_n[i]:
                has_same_prefix = True
                break
        if not has_same_prefix:
            break
    
    # Include the case where we can form numbers with the same length as n
    count += 1 if has_same_prefix else 0
    return count
← Back to All Questions