Get started

Maximum Number of Integers to Choose From a Range I — Medium Problem & Solution

Choose integers from the range [1, n] subject to three rules: each chosen integer appears in banned never, each is chosen at most once, and their total is…

Problem statement

Choose integers from the range [1, n] subject to three rules: each chosen integer appears in banned never, each is chosen at most once, and their total is at most maxSum.

Return the maximum number of integers you can choose.

Example 1

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: Choosing 2 and 4 gives a total of 6.

Example 2

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: Only 8 is allowed and it already exceeds the budget.

Example 3

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: All of 1 through 7 sum to 28.

Constraints

  • 1 <= banned.length <= 10000
  • 1 <= n <= 10000
  • 1 <= maxSum <= 1000000000
  • 1 <= banned[i] <= 10000

How to solve Maximum Number of Integers to Choose From a Range I

The objective counts integers, not their values, so the greedy choice is to take the smallest allowed integers first. Sweeping upward and stopping at the first overflow is optimal.

Approach

  1. Put banned in a set for O(1) rejection.
  2. Walk v from 1 to n, skipping banned values.
  3. If sum + v exceeds maxSum, stop; otherwise add v to the running sum and increment the count.

Why it works

Exchange argument: take any valid selection of size k and replace its largest element with the smallest allowed integer not already chosen — the total never rises and the size is unchanged. Repeating turns any optimal selection into the greedy prefix, so the greedy prefix is optimal.

Complexity

  • Time — O(n + banned.length)
  • Space — O(banned.length)

Pitfalls

  • Continuing past the first overflow does not help — values only grow, so the loop can stop.
  • maxSum reaches a billion, so accumulate in 64 bits in fixed-width languages.
  • Entries of banned may exceed n and are simply irrelevant.

Reference solution

Python

from typing import List

def maxCount(banned: List[int], n: int, maxSum: int) -> int:
    block = set(banned)
    total = 0
    taken = 0
    for v in range(1, n + 1):
        if v in block:
            continue
        if total + v > maxSum:
            break
        total += v
        taken += 1
    return taken

JavaScript

var maxCount = function(banned, n, maxSum) {
    var block = {};
    for (var i = 0; i < banned.length; i++) block[String(banned[i])] = true;
    var sum = 0, taken = 0;
    for (var v = 1; v <= n; v++) {
        if (block[String(v)] === true) continue;
        if (sum + v > maxSum) break;
        sum += v;
        taken++;
    }
    return taken;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 202 hash table problems · the whole catalogue