Jobs

Interviews

Discussions

Maximum Number of Integers to Choose From a Range II

Medium

PayPal

1 view

Topics:

Greedy Algorithms

You are given a closed integer interval [l, r] and an integer array banned.

Return the maximum number of integers you can choose from the interval [l, r] that are not in the banned array and have a sum less than or equal to maxSum.

Example 1:

Input: banned = [1,4,2,3], n = 4, maxSum = 6
Output: 2
Explanation: You can choose the integers [5,6].
Note that the integers 1, 2, 3, and 4 are banned, so you cannot choose them.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer from the interval [1,8] since each integer is banned.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers [1,2,3,4,5,6,7].
Note that the integer 11 is banned, so you cannot choose it.

Constraints:

1 <= banned.length <= 10⁴
1 <= banned[i] <= 10⁵
1 <= n <= 10⁵
1 <= maxSum <= 10⁹

Maximum Number of Integers to Choose From a Range II

Medium

PayPal

1 view

Topics:

Greedy Algorithms

You are given a closed integer interval [l, r] and an integer array banned.

Return the maximum number of integers you can choose from the interval [l, r] that are not in the banned array and have a sum less than or equal to maxSum.

Example 1:

Input: banned = [1,4,2,3], n = 4, maxSum = 6
Output: 2
Explanation: You can choose the integers [5,6].
Note that the integers 1, 2, 3, and 4 are banned, so you cannot choose them.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer from the interval [1,8] since each integer is banned.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers [1,2,3,4,5,6,7].
Note that the integer 11 is banned, so you cannot choose it.

Constraints:

1 <= banned.length <= 10⁴
1 <= banned[i] <= 10⁵
1 <= n <= 10⁵
1 <= maxSum <= 10⁹

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 are the constraints on the size of the `banned` array, and the values of `n` and `maxSum`?
Can the `banned` array contain numbers outside the range `[1, maxSum]`?
If `maxSum` is zero, should I return zero regardless of the `banned` array and `n`?
Is there a specific order in which I should select the integers, or can I choose them in any order that maximizes the count?
If `n` is larger than `maxSum` what do I do?

Brute Force Solution

Approach

The brute force method for this problem involves systematically checking every possible combination of numbers within the given range. We essentially try every subset of numbers to see if it satisfies our constraints. This approach guarantees finding the optimal solution but is highly inefficient.

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

Start by considering an empty set of numbers to choose.
Next, consider sets containing only one number from the allowed range. For each set, check if adding it exceeds the allowed sum or conflicts with any forbidden numbers.
Then, consider all possible sets of two numbers from the range. Again, for each, check the sum and the forbidden numbers.
Continue this process, building sets of increasing sizes (three numbers, four numbers, and so on), always making sure the total sum doesn't go over the limit and that we don't include any forbidden numbers.
Keep track of the size of the largest set that meets all the conditions.
Once all possible combinations have been checked, the largest set size we found is the answer.

Code Implementation

def max_number_of_integers_brute_force(
    number_range_start, number_range_end, forbidden_numbers, maximum_sum
):
    maximum_integers_to_choose = 0

    for i in range(1 << (number_range_end - number_range_start + 1)):
        current_subset = []
        current_sum = 0
        number_count = 0

        for j in range(number_range_end - number_range_start + 1):
            if (i >> j) & 1:
                current_number = number_range_start + j

                # Check if the current number is in the forbidden list.
                if current_number in forbidden_numbers:
                    current_subset = []
                    current_sum = 0
                    number_count = 0
                    break

                current_subset.append(current_number)
                current_sum += current_number
                number_count += 1

        # Prune the search if sum is over the limit 
        if current_sum > maximum_sum:
            continue

        maximum_integers_to_choose = max(
            maximum_integers_to_choose, number_count
        )

    return maximum_integers_to_choose

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers every possible subset of numbers within the given range [start, end], where n = end - start + 1 represents the size of the range. For each number in the range, we have two choices: either include it in our subset or exclude it. This binary decision for each of the n numbers leads to 2^n possible subsets. Checking the validity (sum and forbidden numbers) of each subset takes O(n) time in the worst case, but the dominant factor is the generation and consideration of all 2^n subsets. Therefore, the overall time complexity is O(2^n).

Space Complexity

O(2^N) – The brute force approach described explores all possible subsets of numbers within the range. This means, in the worst-case scenario, we are generating and checking 2^N subsets, where N is the number of integers within the range [start, end] (after excluding the forbidden numbers). While we might not explicitly store all subsets simultaneously, the recursive nature of generating subsets implicitly requires space proportional to the number of subsets considered. Consequently, the auxiliary space is O(2^N) due to the exploration of all possible combinations and intermediate storage during the checking process.

Optimal Solution

Approach

The goal is to pick the most numbers possible from a range, given some numbers we're not allowed to pick and a limit on the sum of our chosen numbers. We use a greedy approach, trying to pick the smallest available numbers first because they take up less of our limited sum, maximizing how many we can ultimately select.

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

First, imagine all possible numbers are lined up in order.
Then, remove the numbers we are not allowed to pick from this line.
Now, start picking numbers from the beginning of the line (the smallest available numbers).
Keep adding numbers until the total sum reaches the limit.
If adding the next smallest number would exceed the limit, stop.
The number of integers you have picked is the maximum you can choose within the rules.

Code Implementation

def max_number_of_integers(number_of_integers, banned_numbers, maximum_sum):

    available_numbers = set(range(1, number_of_integers + 1)) - set(banned_numbers)

    chosen_integers_count = 0
    current_sum = 0

    # Greedily pick the smallest available numbers.
    for number in sorted(available_numbers):
        if current_sum + number <= maximum_sum:
            current_sum += number
            chosen_integers_count += 1
        else:
            # Stop if adding the next number exceeds the limit.
            break

    return chosen_integers_count

Big(O) Analysis

Time Complexity

O(forbidden.length + max_sum) – The first step involves processing the forbidden numbers. Assume forbidden.length is denoted as 'f'. We need to iterate through this array to remove these numbers from the possible numbers. This operation takes O(f) time. The algorithm then iterates, in the worst case, up to max_sum to pick numbers greedily. The maximum number we can pick is limited by the max_sum. So this step takes O(max_sum). Therefore, the overall time complexity is O(f + max_sum).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that conceptually filters and selects numbers. It doesn't explicitly mention the creation of any auxiliary data structures like arrays, sets, or hash maps to store intermediate results or track available numbers. Only a few constant space variables are needed for iteration and sum tracking. Thus, the auxiliary space used is constant, independent of the input size.

Edge Cases

Case	How to Handle
banned is null or empty	If banned is null or empty, proceed without filtering any numbers from the range 1 to maxSum.
maxSum is zero	If maxSum is zero, no integers can be chosen, so return 0.
n is zero	If n is zero, return 0 as no numbers will be selected from 1 to maxSum.
banned contains numbers outside the range [1, maxSum]	Ignore numbers in banned that are outside of the range [1, maxSum] since they cannot be chosen anyway.
banned contains duplicate numbers	Treat duplicate numbers in banned as a single ban, a set or hashmap efficiently handles this.
maxSum is very large, leading to potential integer overflow	Ensure that the running sum of selected numbers uses a data type large enough to prevent integer overflow, such as long.
All numbers in the range [1, maxSum] are banned	If all numbers in the range are banned, return 0 as no numbers can be chosen.
maxSum is smaller than 1	If maxSum is less than 1 return 0, as the range [1, maxSum] will be empty or invalid.

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 are the constraints on the size of the `banned` array, and the values of `n` and `maxSum`?
Can the `banned` array contain numbers outside the range `[1, maxSum]`?
If `maxSum` is zero, should I return zero regardless of the `banned` array and `n`?
Is there a specific order in which I should select the integers, or can I choose them in any order that maximizes the count?
If `n` is larger than `maxSum` what do I do?

Brute Force Solution

Approach

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

Start by considering an empty set of numbers to choose.
Next, consider sets containing only one number from the allowed range. For each set, check if adding it exceeds the allowed sum or conflicts with any forbidden numbers.
Then, consider all possible sets of two numbers from the range. Again, for each, check the sum and the forbidden numbers.
Continue this process, building sets of increasing sizes (three numbers, four numbers, and so on), always making sure the total sum doesn't go over the limit and that we don't include any forbidden numbers.
Keep track of the size of the largest set that meets all the conditions.
Once all possible combinations have been checked, the largest set size we found is the answer.

Code Implementation

def max_number_of_integers_brute_force(
    number_range_start, number_range_end, forbidden_numbers, maximum_sum
):
    maximum_integers_to_choose = 0

    for i in range(1 << (number_range_end - number_range_start + 1)):
        current_subset = []
        current_sum = 0
        number_count = 0

        for j in range(number_range_end - number_range_start + 1):
            if (i >> j) & 1:
                current_number = number_range_start + j

                # Check if the current number is in the forbidden list.
                if current_number in forbidden_numbers:
                    current_subset = []
                    current_sum = 0
                    number_count = 0
                    break

                current_subset.append(current_number)
                current_sum += current_number
                number_count += 1

        # Prune the search if sum is over the limit 
        if current_sum > maximum_sum:
            continue

        maximum_integers_to_choose = max(
            maximum_integers_to_choose, number_count
        )

    return maximum_integers_to_choose

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, imagine all possible numbers are lined up in order.
Then, remove the numbers we are not allowed to pick from this line.
Now, start picking numbers from the beginning of the line (the smallest available numbers).
Keep adding numbers until the total sum reaches the limit.
If adding the next smallest number would exceed the limit, stop.
The number of integers you have picked is the maximum you can choose within the rules.

Code Implementation

def max_number_of_integers(number_of_integers, banned_numbers, maximum_sum):

    available_numbers = set(range(1, number_of_integers + 1)) - set(banned_numbers)

    chosen_integers_count = 0
    current_sum = 0

    # Greedily pick the smallest available numbers.
    for number in sorted(available_numbers):
        if current_sum + number <= maximum_sum:
            current_sum += number
            chosen_integers_count += 1
        else:
            # Stop if adding the next number exceeds the limit.
            break

    return chosen_integers_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
banned is null or empty	If banned is null or empty, proceed without filtering any numbers from the range 1 to maxSum.
maxSum is zero	If maxSum is zero, no integers can be chosen, so return 0.
n is zero	If n is zero, return 0 as no numbers will be selected from 1 to maxSum.
banned contains numbers outside the range [1, maxSum]	Ignore numbers in banned that are outside of the range [1, maxSum] since they cannot be chosen anyway.
banned contains duplicate numbers	Treat duplicate numbers in banned as a single ban, a set or hashmap efficiently handles this.
maxSum is very large, leading to potential integer overflow	Ensure that the running sum of selected numbers uses a data type large enough to prevent integer overflow, such as long.
All numbers in the range [1, maxSum] are banned	If all numbers in the range are banned, return 0 as no numbers can be chosen.
maxSum is smaller than 1	If maxSum is less than 1 return 0, as the range [1, maxSum] will be empty or invalid.