Maximum Number of Integers to Choose From a Range I

Medium

PayPal

1 view

Topics:

ArraysGreedy Algorithms

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

The chosen integers have to be in the range [1, n].
Each integer can be chosen at most once.
The chosen integers should not be in the array banned.
The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints:

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

Maximum Number of Integers to Choose From a Range I

Medium

PayPal

1 view

Topics:

ArraysGreedy Algorithms

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

The chosen integers have to be in the range [1, n].
Each integer can be chosen at most once.
The chosen integers should not be in the array banned.
The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.

Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.

Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.

Constraints:

1 <= banned.length <= 10⁴
1 <= banned[i], 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 values of `banned`, `n`, and `maxSum`? What are their maximum and minimum possible values?
Is the `banned` array guaranteed to contain unique numbers, or could there be duplicates?
If it's not possible to pick any numbers without exceeding `maxSum` (even just the smallest number 1), what should I return? Should I return 0?
Is `n` guaranteed to be greater than or equal to 1?
Are all the numbers in the `banned` array within the range [1, n]? Or could there be numbers outside this range?

Brute Force Solution

Approach

The brute force approach involves checking every possible combination of numbers within the range. We try including each number one by one, and then see if we can include more numbers while staying within the cost limit and avoiding the banned numbers. We repeat this for every possible starting point.

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

Start by considering each number within the given range as a possible candidate to include.
For each candidate, check if it is a banned number. If it is, skip it and move on to the next number.
If the number is not banned, check if including it would exceed the maximum cost allowed.
If including the number would exceed the cost, skip it and move on.
If including the number is allowed, add it to the selection and reduce the cost accordingly.
Repeat this process for all subsequent numbers in the range, always checking if they are banned and if adding them exceeds the cost.
Keep track of the maximum number of integers that could be selected without exceeding the cost or including banned numbers, across all possible starting numbers.
After checking all possible starting numbers in the range, the largest number of integers tracked will be the final answer.

Code Implementation

def max_number_of_integers(number_range, banned_numbers, maximum_cost):
    max_integers_selected = 0

    for start_number in range(1, number_range + 1):
        integers_selected = 0
        current_cost = maximum_cost
        selected_numbers = []

        for current_number in range(start_number, number_range + 1):
            if current_number in banned_numbers:
                continue

            # Check if adding the number exceeds the remaining cost
            if current_number > current_cost:

                continue

            # Deduct the cost and increment selected integers
            current_cost -= current_number
            integers_selected += 1
            selected_numbers.append(current_number)

        # Update maximum integers if current selection is better
        max_integers_selected = max(max_integers_selected, integers_selected)

    return max_integers_selected

Big(O) Analysis

Time Complexity

O(maxRange * maxRange) – The algorithm iterates through each number in the range [1, maxRange] as a potential starting point. For each starting point, it iterates through the remaining numbers in the range to check if they can be included. In the worst-case scenario, for a large maxRange value, this leads to a nested loop structure where the outer loop runs up to maxRange times and the inner loop also runs up to maxRange times. Therefore, the total number of operations approximates maxRange * maxRange, which simplifies to O(maxRange * maxRange).

Space Complexity

O(1) – The provided brute force approach iterates through the numbers in the range and checks for banned numbers and cost limits. It implicitly uses a counter to keep track of the number of integers selected so far and a variable to store the maximum count found across all iterations. These counters and variables consume constant extra space regardless of the input range or the number of banned integers, hence the space complexity is O(1).

Optimal Solution

Approach

The goal is to pick as many numbers as possible from a given range while avoiding certain forbidden numbers, and staying within a budget. The best strategy is to greedily pick the smallest available numbers that aren't forbidden, until you run out of budget.

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

First, identify and remove all the forbidden numbers from the range of available numbers.
Then, sort the remaining available numbers in ascending order.
Start with the smallest available number, and check if adding it to your selection will exceed your budget.
If the number fits within the budget, include it in your selection and reduce the budget accordingly.
Continue this process with the next smallest available number, and so on.
Keep selecting numbers until you either run out of available numbers or your budget is exhausted.
The total count of numbers selected will be your maximum possible count.

Code Implementation

def max_number_of_integers(number_of_integers, maximum_sum, forbidden_numbers):
    available_numbers = []
    for number in range(1, number_of_integers + 1):
        if number not in forbidden_numbers:
            available_numbers.append(number)

    available_numbers.sort()

    count_of_chosen_integers = 0
    current_sum = 0

    for number in available_numbers:
        # Check if adding the current number exceeds the maximum sum
        if current_sum + number <= maximum_sum:
            current_sum += number
            count_of_chosen_integers += 1

        # If the budget is exhausted, stop selecting numbers
        else:
            break

    return count_of_chosen_integers

Big(O) Analysis

Time Complexity

O(n log n) – Let n be the size of the range [1, max_sum] and m be the number of forbidden integers. First, identifying and removing forbidden numbers from the range takes O(m) time if we use a set data structure for forbidden numbers, where m <= n. Then, sorting the remaining available numbers takes O(n log n) time. The subsequent greedy selection iterates through the sorted numbers at most once, taking O(n) time. Thus, the dominant operation is the sorting step, resulting in a time complexity of O(n log n).

Space Complexity

O(N) – The algorithm first removes forbidden numbers from the range. This implies the creation of a data structure, such as a set or a boolean array, to efficiently check for forbidden numbers, which could take up space proportional to the size of the range (n = right - left + 1). Additionally, the available numbers are then sorted, requiring additional space for sorting, which could be O(N) in the worst case depending on the sorting algorithm used. Therefore, the auxiliary space needed is O(N), where N is the size of the range.

Edge Cases

Case	How to Handle
n is 0 or less	Return 0, as there are no numbers to choose from the range.
maxSum is 0 or less	Return 0, as no positive integers can be selected without exceeding the sum.
banned is null or empty	Treat it as if no numbers are banned, proceeding with the selection process.
banned contains duplicates	The set conversion implicitly handles duplicates, only storing unique banned numbers.
banned contains numbers outside the range [1, n]	These numbers are irrelevant and should be ignored during selection, as they cannot be picked.
n is very large, close to Integer.MAX_VALUE	Ensure the running sum does not overflow during integer addition by using long if necessary.
maxSum is small but n is extremely large	The solution might iterate through most of the numbers from 1 to maxSum before finding a banned number or exceeding maxSum; the algorithm should handle this inefficiency if possible (e.g., optimize the loop condition).
All numbers in the range [1, n] are banned	Return 0, as no numbers can be selected.