Maximum Number of Integers to Choose From a Range I

MEDIUM

Description

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⁹

Approaches

Checkout 2 different approaches to solve Maximum Number of Integers to Choose From a Range I. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Linear Scan

This approach uses a greedy strategy by iterating through numbers from 1 to n and picking the smallest available integers first. To check if a number is banned, it performs a simple linear scan through the banned array. This is the most straightforward but also the least efficient method.

Algorithm

Initialize count of chosen integers to 0 and currentSum (as a long to prevent overflow) to 0.
Iterate with a number i from 1 to n.
For each i, perform a linear scan through the banned array to check if i is present.
If i is not in banned and currentSum + i does not exceed maxSum:
- Increment count.
- Add i to currentSum.
If currentSum + i exceeds maxSum, stop the process as any subsequent number will also exceed the limit.
Return the final count.

The core idea is to maximize the number of chosen integers. A greedy strategy works best here: by always choosing the smallest possible integers, we leave the maximum possible budget in maxSum for subsequent integers.

The algorithm proceeds as follows:

Initialize a counter count to 0 and a running sum currentSum to 0. We use a long for currentSum to avoid potential overflow since maxSum can be large.
We loop through each integer i from 1 to n.
For each i, we first check if we can afford to add it. If currentSum + i > maxSum, we break the loop because any number greater than i will also violate the condition.
If we can afford i, we then check if it's a banned number. This is done by iterating through the entire banned array. A flag, isBanned, can be used to track this.
If i is not banned, we choose it: increment count and add i to currentSum.
After the loop finishes (either by reaching n or by exceeding maxSum), we return the final count.

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        long currentSum = 0;
        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (currentSum + i > maxSum) {
                break;
            }

            boolean isBanned = false;
            for (int b : banned) {
                if (b == i) {
                    isBanned = true;
                    break;
                }
            }

            if (!isBanned) {
                currentSum += i;
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n * B), where `n` is the upper limit of the range and `B` is the length of the `banned` array. The outer loop runs up to `n` times, and for each iteration, we scan the `banned` array, which takes `O(B)` time.Space Complexity: O(1), as we only use a few variables to store the state, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Very low memory usage as it doesn't require any extra data structures.

Cons:

Highly inefficient for the given constraints, with a time complexity of O(n * B). This is likely to cause a 'Time Limit Exceeded' error on most coding platforms.

Code Solutions

Checking out 3 solutions in different languages for Maximum Number of Integers to Choose From a Range I. Click on different languages to view the code.

class Solution {
public
  int maxCount(int[] banned, int n, int maxSum) {
    Set<Integer> ban = new HashSet<>(banned.length);
    for (int x : banned) {
      ban.add(x);
    }
    int ans = 0, s = 0;
    for (int i = 1; i <= n && s + i <= maxSum; ++i) {
      if (!ban.contains(i)) {
        ++ans;
        s += i;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Maximum Number of Integers to Choose From a Range I

Algorithms:

Binary SearchSorting

Patterns:

Greedy

Data Structures:

ArrayHash Table

Companies:

PayPal |