Maximum Number of Integers to Choose From a Range I

Medium
669.

Maximum Number of Integers to Choose From a Range I

Maximum Number of Integers to Choose From a Range I is a medium coding problem on hash table, greedy and binary search, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} banned
 * @param {number} n
 * @param {number} maxSum
 * @return {number}
 */
var maxCount = function(banned, n, maxSum) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Integers to Choose From a Range I Solution

Maximum Number of Integers to Choose From a Range I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Integers to Choose From a Range I is a medium coding problem on hash table, greedy and binary search, asked in Amazon, Google and Flipkart interviews.

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

Hints for Maximum Number of Integers to Choose From a Range I

  1. Hint 1

    To maximise the count under a sum budget, always prefer smaller numbers.

  2. Hint 2

    So walk 1, 2, 3, … in order, skipping banned values, and take each one while it still fits.

  3. Hint 3

    Stop as soon as the next allowed value would overflow the budget — every later value is at least as large.

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

Java

public static int maxCount(int[] banned, int n, int maxSum) {
    Set<Integer> block = new HashSet<>();
    for (int b : banned) block.add(b);
    long sum = 0;
    int taken = 0;
    for (int v = 1; v <= n; v++) {
        if (block.contains(v)) continue;
        if (sum + v > maxSum) break;
        sum += v;
        taken++;
    }
    return taken;
}

C++

int maxCount(vector<int>& banned, int n, int maxSum) {
    unordered_set<int> block(banned.begin(), banned.end());
    long long sum = 0;
    int taken = 0;
    for (int v = 1; v <= n; v++) {
        if (block.count(v)) continue;
        if (sum + v > maxSum) break;
        sum += v;
        taken++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Greedy Algorithms