Scale Engineer

Maximum Number of Integers to Choose From a Range I

Med
#2334Time: 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: O(1), as we only use a few variables to store the state, regardless of the input size.1 company
Patterns
Greedy
Algorithms
Binary SearchSorting
Data structures
ArrayHash Table
Companies
PayPal

Prompt

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 <= 104
  • 1 <= banned[i], n <= 104
  • 1 <= maxSum <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. 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.
  2. We loop through each integer i from 1 to n.
  3. 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.
  4. 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.
  5. If i is not banned, we choose it: increment count and add i to currentSum.
  6. 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

Time

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

O(1), as we only use a few variables to store the state, regardless of the input size.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem