Problem of The Day: Maximum Number of Integers to Choose From a Range I

Problem Statement

Intuition

The problem can be approached by iteratively considering all numbers from 1 to n and determining whether they can be included in the sum without violating the constraints:

1. The number must not be in the banned list.
2. The cumulative sum of the selected numbers must not exceed maxSum.

This approach ensures that we maximize the count of numbers that can be included while adhering to the restrictions.

Approach

1. Convert the banned list into a set for O(1) lookup times.
2. Initialize variables res to keep track of the current sum and count to count the numbers added.
3. Iterate through numbers from 1 to n:
   • Skip the number if it is banned.
   • Skip the number if adding it would exceed maxSum.
   • Otherwise, add the number to the cumulative sum (res) and increment the count (count).
4. Return the total count of numbers added.

Complexity

• Time complexity:
  \(O(n)\)
  Iterating through numbers from 1 to n takes O(n), and checking membership in the banned set is O(1).

• Space complexity:
  \(O(b)\)
  Where b is the size of the banned list, as it is converted into a set.

Code

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_numbers = set(banned)
        res = 0
        count = 0
        for x in range(1, n + 1):
            if x in banned_numbers:
                continue
            if res + x > maxSum:
                continue
            res += x
            count += 1
        return count

Editorial

Approach 1: Binary Search

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        # Sort banned array to enable binary search
        banned.sort()
        count = 0

        # Try each number from 1 to n
        for num in range(1, n + 1):
            # Skip if number is in banned array
            if self._custom_binary_search(banned, num):
                continue

            maxSum -= num
            # Break if sum exceeds our limit
            if maxSum < 0:
                break

            count += 1

        return count

    def _custom_binary_search(self, arr: List[int], target: int) -> bool:
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return True
            if arr[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return False

Approach 2: Sweep

class Solution:
    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
        # Sort the banned list
        banned.sort()

        banned_idx = 0
        count = 0

        # Check each number from 1 to n while the sum is valid
        for num in range(1, n + 1):
            # Skip if the current number is in the banned list
            if banned_idx < len(banned) and banned[banned_idx] == num:
                # Handle duplicate banned numbers
                while banned_idx < len(banned) and banned[banned_idx] == num:
                    banned_idx += 1
            else:
                # Include the current number if possible
                maxSum -= num
                if maxSum >= 0:
                    count += 1
                else:
                    break

        return count

Approach 3: Hash Set

class Solution:
    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
        # Store banned numbers in a set for quick lookup
        banned_set = set(banned)

        count = 0

        # Try each number from 1 to n
        for num in range(1, n + 1):
            # Skip banned numbers
            if num in banned_set:
                continue

            # Return if adding the current number exceeds maxSum
            if maxSum - num < 0:
                return count

            # Include current number
            maxSum -= num
            count += 1

        return count