Maximum Number of Integers to Choose From a Range I

Problem Description

Ah, the classic dilemma of choosing numbers! Imagine you’re at a buffet, and you can only pick a certain number of dishes without exceeding your calorie limit. But wait! Some dishes are banned because they might ruin your diet (or your taste buds). This is essentially what the “Maximum Number of Integers to Choose From a Range I” problem is all about.

In this problem, you’re given a range of integers from 1 to n, and a list of banned integers. Your task is to select as many integers as possible from this range without exceeding a given sum, maxSum. It’s like trying to pick the best snacks at a party while avoiding the ones that might give you a stomach ache!

Code Solution


class Solution {
  public int maxCount(int[] banned, int n, int maxSum) {
    int ans = 0;
    int sum = 0;
    Set bannedSet = Arrays.stream(banned).boxed().collect(Collectors.toSet());

    for (int i = 1; i <= n; ++i)
      if (!bannedSet.contains(i) && sum + i <= maxSum) {
        ++ans;
        sum += i;
      }

    return ans;
  }
}

Approach Explanation

The approach here is straightforward yet effective. We create a set of banned integers for quick look-up. Then, we iterate through the integers from 1 to n, checking if each integer is banned and if adding it to our current sum would exceed maxSum. If both conditions are satisfied, we include the integer in our count and update the sum. It’s like a game of "Will it fit?" but with numbers!

Time and Space Complexity

Time Complexity: O(n + b), where n is the range of integers and b is the number of banned integers. We iterate through the range and check against the banned set.

Space Complexity: O(b), for storing the banned integers in a set.

Real-World Example

Let’s say you’re at a party with a budget of $100. You want to buy snacks (integers) from a menu (1 to n), but some snacks are banned because they’re too expensive or just plain weird (banned integers). You want to maximize the number of snacks you can buy without going over your budget. This problem is a perfect analogy for that scenario!