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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Integers to Choose From a Range II

Number: 2702

Difficulty: Medium

Paid? Yes

Companies: PayPal

Problem Description

Given an integer array banned and two integers n and maxSum, choose some numbers following these rules:

  • The chosen integers must be in the range [1, n].
  • Each integer can be chosen at most once.
  • None of the chosen integers appear in banned.
  • The sum of the chosen integers does not exceed maxSum.

Return the maximum number of integers that can be chosen under these conditions.

Key Insights

  • To maximize the count, we should always choose the smallest allowed integers.
  • The allowed integers are those in [1, n] excluding the banned ones.
  • Instead of iterating over every candidate from 1 to n (which is not feasible for large n), notice that the allowed numbers are nearly continuous segments between banned values.
  • Process the continuous intervals in increasing order and, for each interval, determine how many consecutive numbers you can add before the sum constraint is reached.
  • Use the arithmetic series sum formula for consecutive integers and a binary search (or mathematical calculation) to determine the maximum count that can be taken from a given interval.

Space and Time Complexity

Time Complexity: O(m log(Δ)) where m is the number of banned numbers and Δ is the length of an interval. In the worst-case m = 10^5. Space Complexity: O(m), for storing the banned numbers in a set or sorted list.

Solution

We first sort the banned numbers and convert them into a set for quick look-up. Then we consider the allowed intervals:

  1. The interval from 1 to banned[0] - 1 (if it exists).
  2. Each interval between banned[i] and banned[i+1] (i.e. from banned[i] + 1 to banned[i+1] - 1).
  3. The interval from banned[-1] + 1 to n.

For each interval, we try to take as many integers as possible from the beginning of that interval without exceeding the maxSum limit. Since the numbers in each interval are consecutive, the sum for taking x numbers starting from L is:   sum = xL + (x(x-1)) / 2

We use a binary search (or mathematical derivation) on x to find the maximum number we can take from the current interval such that the overall running sum does not exceed maxSum. We update our count and the current sum accordingly. If the next interval would cause the sum to exceed maxSum, we stop.

This greedy approach ensures that we always pick the smallest allowed numbers to maximize the count.

Code Solutions

# Python solution using binary search on each interval
def maxCount(banned, n, maxSum):
    # Sort the banned numbers and remove duplicates, only consider those <= n.
    banned = sorted(set(x for x in banned if x <= n))
    chosen_count = 0
    current_sum = 0

    # Helper function: Given start L, maximum x numbers you can pick from interval [L, R]
    # where R is not necessarily used in calculation because we calculate only up to available gap.
    def max_take_from_interval(L, available):
        # We need to solve for x from: current_sum + (x*L + (x*(x-1))//2) <= maxSum
        lo, hi = 0, available
        best = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            # Sum needed if we take mid numbers starting at L
            required = mid * L + (mid * (mid - 1)) // 2
            if current_sum + required <= maxSum:
                best = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return best

    prev_end = 0  # previous banned number boundary, start with 0
    # Process intervals between 1 and n
    for b in banned:
        # Allowed interval is from prev_end+1 to b-1
        L = prev_end + 1
        R = b - 1
        if L <= R:
            available = R - L + 1
            # Find how many numbers we can add from this interval.
            take = max_take_from_interval(L, available)
            chosen_count += take
            # Update current sum with sum of arithmetic progression: take numbers from L
            current_sum += take * L + (take * (take - 1)) // 2
            if current_sum == maxSum or take < available:
                return chosen_count
        prev_end = b

    # Process the last interval from last banned + 1 to n
    L = prev_end + 1
    if L <= n:
        available = n - L + 1
        take = max_take_from_interval(L, available)
        chosen_count += take
    return chosen_count

# Example usage:
print(maxCount([4, 3, 5, 6], 7, 18))  # Output: 3
← Back to All Questions