We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Integers to Choose From a Range I

Number: 2640

Difficulty: Medium

Paid? No

Companies: PayPal

Problem Description

Given an integer array banned, an integer n, and an integer maxSum, select a subset of integers from the range [1, n] such that:

  • Each integer is chosen at most once.
  • None of the integers is present in the banned array.
  • The sum of the chosen integers does not exceed maxSum. Return the maximum number of integers that can be chosen while satisfying these rules.

Key Insights

  • Use a set for banned numbers to allow quick lookups.
  • Greedily select the smallest numbers from 1 to n to maximize the count, as smaller numbers allow for a minimal sum.
  • Maintain a running sum and count; stop when adding the next eligible number would exceed maxSum.
  • The approach is simple and efficient given the constraints.

Space and Time Complexity

Time Complexity: O(n) (plus O(m) for creating the banned set, where m is the length of banned, overall linear) Space Complexity: O(n) (due to storing banned numbers in a set)

Solution

The solution uses a greedy algorithm. First, convert the banned list into a set for O(1) membership checks. Then, iterate through integers from 1 to n. For each integer, if it is not in the banned set and adding it to the current sum does not exceed maxSum, then include it and update the sum and counter. The iteration stops either when all numbers have been considered or when the next eligible integer would make the sum exceed maxSum.

Code Solutions

# Python solution with line-by-line comments

def maxCount(banned, n, maxSum):
    # Convert the banned list to a set for O(1) lookups
    banned_set = set(banned)
    
    current_sum = 0  # Initialize the running sum
    count = 0        # Initialize the count of chosen integers
    
    # Iterate over numbers from 1 to n
    for number in range(1, n + 1):
        # Check if the number is not banned and sum does not exceed maxSum
        if number not in banned_set and current_sum + number <= maxSum:
            current_sum += number  # Update the running sum
            count += 1             # Increment the count
        # If adding the current number exceeds maxSum, we break early
        elif current_sum + number > maxSum:
            break
    
    return count

# Example usage:
print(maxCount([1, 6, 5], 5, 6))  # Expected output: 2
← Back to All Questions