Maximum Number of Integers to Choose From a Range I

Problem Description

Ah, the classic dilemma of choosing integers! 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’re just too unhealthy (or maybe they just don’t taste good). This problem is like that, but instead of food, we’re dealing with integers.

The task is to find out how many integers you can choose from a range of 1 to n, without picking any banned integers and without exceeding a maximum sum. It’s like trying to eat your favorite dishes while avoiding the ones that make you cringe, all while keeping your calorie count in check.

Code Solution


class Solution:
    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
        ans = 0
        summ = 0
        bannedSet = set(banned)

        for i in range(1, n + 1):
            if i not in bannedSet and summ + i <= maxSum:
                ans += 1
                summ += i

        return ans

Approach

The approach here is straightforward yet effective. We maintain a running total of the sum of the integers we can choose. We iterate through each integer from 1 to n, checking if it’s not banned and if adding it to our current sum doesn’t exceed the maximum allowed sum. If both conditions are satisfied, we include it in our count and update our sum. It’s like a game of “Will it fit?” but with numbers!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n) - We iterate through the range of integers from 1 to n.
Space Complexity	O(k) - Where k is the number of banned integers, as we store them in a set for quick lookup.

Real-World Example

Let’s say you’re at a party with a limited budget (maxSum) and a list of drinks you can’t have (banned). You want to maximize the number of different drinks you can try without going over your budget. This problem is just like that! You’re trying to pick the maximum number of drinks (integers) while avoiding the ones you can’t have (banned) and staying within your budget (maxSum).