Numbers At Most N Given Digit Set

Hard

Asked by:

55 views

Topics:

ArraysStringsDynamic Programming

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. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2:

Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation: 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.

Example 3:

Input: digits = ["7"], n = 8
Output: 1

Constraints:

1 <= digits.length <= 9
digits[i].length == 1
digits[i] is a digit from '1' to '9'.
All the values in digits are unique.
digits is sorted in non-decreasing order.
1 <= n <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for N and the length of the digit set?
Can the digits in the digit set contain leading zeros?
If N is 0, or the digit set is empty, what should I return?
Is N guaranteed to be a positive integer?
Are the digits in the digit set guaranteed to be sorted in ascending order?

Brute Force Solution

Approach

The brute force approach involves generating every possible number that can be formed using the given digits and then checking if each generated number is less than or equal to the target number. We explore all possible combinations of digits up to the length of the target number. This method guarantees finding all valid numbers, but it might be slow for large target numbers or a larger digit set.

Here's how the algorithm would work step-by-step:

First, determine the number of digits in the target number.
Start by considering all possible single-digit numbers formed using the available digits.
Check each single-digit number to see if it is less than or equal to the target number. If it is, count it.
Now, consider all possible two-digit numbers formed using the available digits.
Check each two-digit number to see if it is less than or equal to the target number. If it is, count it.
Repeat this process for three-digit numbers, four-digit numbers, and so on, up to the number of digits in the target number.
Each time, you're creating all possible numbers of a specific length using the given digits and checking if they're valid (less than or equal to the target number).
Finally, add up all the valid numbers you've counted from each step to get the total number of valid numbers.

Code Implementation

def numbers_at_most_n_given_digit_set_brute_force(digits, number_limit):
    number_limit_string = str(number_limit)
    number_limit_length = len(number_limit_string)
    count_of_valid_numbers = 0

    for current_length in range(1, number_limit_length + 1):
        count_of_valid_numbers += count_valid_numbers_of_length(
            digits, current_length, number_limit_string
        )

    return count_of_valid_numbers

def count_valid_numbers_of_length(digits, current_length, number_limit_string):
    count_of_valid_numbers = 0

    # Generate all possible numbers of currentLength using digits.
    possible_numbers = generate_all_possible_numbers(digits, current_length)

    # Count how many of the generated numbers are valid.
    for number in possible_numbers:
        if int(number) <= int(number_limit_string):
            count_of_valid_numbers += 1

    return count_of_valid_numbers

def generate_all_possible_numbers(digits, current_length):
    if current_length == 0:
        return ['']

    if current_length == 1:
        return digits

    possible_numbers = []
    for digit in digits:
        # Recursively find all numbers of smaller length
        smaller_numbers = generate_all_possible_numbers(digits, current_length - 1)
        for smaller_number in smaller_numbers:
            possible_numbers.append(digit + smaller_number)

    return possible_numbers

Big(O) Analysis

Time Complexity

O(L * K^L) – Let L be the number of digits in the target number N and K be the number of digits in the given digit set. The algorithm iterates through all possible numbers with lengths from 1 to L. For each length i, it generates K^i possible numbers. Therefore, the total number of generated numbers is K^1 + K^2 + ... + K^L. This sum is dominated by the term K^L. For each generated number of length L, we also need to compare it with N which takes O(L) time. Therefore, the overall time complexity is O(L * K^L).

Space Complexity

O(1) – The described brute force approach generates and checks each number individually. While it implicitly iterates through possible numbers of varying lengths (up to the length of N), these generated numbers are not stored in any auxiliary data structure. The comparison and counting happen in place, requiring only a few constant space variables to keep track of the count and current number being generated, regardless of the size of N. Therefore, the space complexity is constant.

Optimal Solution

Approach

We want to count how many numbers we can make using a given set of digits, where those numbers are no bigger than a target number. The key is to compare the digits of our target number with the allowed digits, one position at a time. This lets us avoid checking every single possible number.

Here's how the algorithm would work step-by-step:

First, count how many numbers we can make that are shorter than our target number. This is easy because we know the length and the available digits.
Now, focus on numbers that have the same length as our target number. Go through the digits of the target number from left to right, one at a time.
At each digit position of the target number, check how many of our allowed digits are smaller than the digit in the target number. Each of these smaller digits can start a valid number for this length, so count them.
If one of our allowed digits is exactly equal to the digit in the target number, we need to continue to the next digit position of the target number. If none of our allowed digits are equal to the current digit in the target number, we stop, because any number we build from there will be too big.
If we make it all the way to the end of the target number and one of our allowed digits was equal to each of the digits in the target number, then we can also form the target number itself, so we increment our count.
Add up all the counts we got from the shorter numbers and the same-length numbers. This gives us the total count of numbers we can make.

Code Implementation

def numbers_at_most_n_given_digit_set(digits, number_limit):
    number_as_string = str(number_limit)
    number_length = len(number_as_string)
    count = 0

    # Count numbers shorter than the limit
    for length in range(1, number_length): 
        count += len(digits) ** length

    for index, digit_from_number in enumerate(number_as_string):
        suitable_digits = [digit for digit in digits if digit < digit_from_number]

        # Add numbers that are smaller at this position
        count += len(suitable_digits) * (len(digits) ** (number_length - index - 1))

        # If we find an exact match, continue to the next digit.
        if digit_from_number in digits:
            if index == number_length - 1:
                count += 1
        else:
            break

    return count

Big(O) Analysis

Time Complexity

O(logN) – The algorithm iterates through the digits of the target number N, where N is the input number. The number of digits in N is logarithmic with respect to its value (logarithmic base 10). Within the loop, we perform constant-time operations like comparing digits and summing results. Therefore, the time complexity is determined by the number of digits in N, which is O(logN).

Space Complexity

O(1) – The described algorithm primarily uses a few integer variables to keep track of the count of valid numbers and iterate through the digits of the input number N. It doesn't create any auxiliary data structures like arrays, lists, or hash maps that scale with the size of N or the number of allowed digits. Therefore, the space complexity remains constant regardless of the input, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty Digit Set	Return 0 since no numbers can be formed if no digits are allowed
N is a single digit number	Count the number of digits in the digit set that are less than or equal to N
N is a number with leading zeros	Treat N as its integer representation (remove leading zeros)
Digit set contains '0' and N is large	Handle cases where using '0' at the beginning is not allowed when forming numbers less than N.
N has repeating digits and digit set contains duplicates	The algorithm must ensure to correctly count all combinations without overcounting from either repeated digits in N or duplicates in the digit set.
Very large N leading to potential integer overflow in intermediate calculations	Use appropriate data types (e.g., long) to avoid overflow during calculations involving powers of the digit set size.
Digit Set contains digits larger than the leading digit of N	Skip considering digits in the digit set that are already larger than the first digit of N when calculating the count for the first digit position.
N consists of only the largest available digit	Ensure the algorithm correctly accounts for the number N itself and all the numbers smaller than it which can be formed from the digit set.

Empty Digit Set

How to Handle:

Return 0 since no numbers can be formed if no digits are allowed

N is a single digit number

How to Handle:

Count the number of digits in the digit set that are less than or equal to N

N is a number with leading zeros

How to Handle:

Treat N as its integer representation (remove leading zeros)

Digit set contains '0' and N is large

How to Handle:

Handle cases where using '0' at the beginning is not allowed when forming numbers less than N.

N has repeating digits and digit set contains duplicates

How to Handle:

The algorithm must ensure to correctly count all combinations without overcounting from either repeated digits in N or duplicates in the digit set.

Very large N leading to potential integer overflow in intermediate calculations

How to Handle:

Use appropriate data types (e.g., long) to avoid overflow during calculations involving powers of the digit set size.

Digit Set contains digits larger than the leading digit of N

How to Handle:

Skip considering digits in the digit set that are already larger than the first digit of N when calculating the count for the first digit position.

N consists of only the largest available digit

How to Handle:

Ensure the algorithm correctly accounts for the number N itself and all the numbers smaller than it which can be formed from the digit set.