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 day). This is essentially what the “Maximum Number of Integers to Choose From a Range I” problem is all about. You have a range of integers from 1 to n, but some of them are on the “do not eat” list (banned). Your task? Pick as many integers as you can without exceeding a given sum. It’s like trying to eat all the desserts at a party while avoiding the ones that might give you a sugar rush!

Code Solution


class Solution {
 public:
  int maxCount(vector& banned, int n, int maxSum) {
    int ans = 0;
    int sum = 0;
    const unordered_set bannedSet{banned.begin(), banned.end()};

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

    return ans;
  }
};

Approach

The approach here is straightforward yet effective. We maintain a running total of the sum of integers we can choose. 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 the maximum allowed sum. If both conditions are satisfied, we include the integer in our count and update our sum. It’s like a game of Tetris, where you’re trying to fit as many blocks as possible without going over the edge!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(b)

Real-World Example

Let’s say you’re at a party with a limited budget for snacks. You can choose from a variety of snacks (1 to n), but some are off-limits because they’re too expensive or just plain weird (banned). You want to maximize the number of snacks you can enjoy without blowing your budget. This problem mirrors that scenario perfectly!