Maximum Number of Integers to Choose From a Range I
Problem
Given an array banned and integers n and maxSum, choose integers from the range [1, n]. Each integer may be chosen at most once, no chosen integer may appear in banned, and the sum of chosen integers must not exceed maxSum. Return the maximum count of integers you can choose.
To maximize how many numbers fit under the budget, always prefer the smallest available value first — small numbers cost less, leaving more room for further picks.
banned = [1,6,5], n = 5, maxSum = 62def maxCount(banned, n, maxSum):
# Only banned values inside [1, n] can ever interfere.
blocked = {b for b in banned if b <= n}
total = 0 # running sum of chosen integers
count = 0 # how many we have chosen
# Greedy: smallest allowed numbers first.
for num in range(1, n + 1):
if num in blocked:
continue
if total + num > maxSum:
break # budget would be exceeded
total += num
count += 1
return countfunction maxCount(banned, n, maxSum) {
// Only banned values inside [1, n] can ever interfere.
const blocked = new Set(banned.filter(b => b <= n));
let total = 0; // running sum of chosen integers
let count = 0; // how many we have chosen
// Greedy: smallest allowed numbers first.
for (let num = 1; num <= n; num++) {
if (blocked.has(num)) continue;
if (total + num > maxSum) break; // budget exceeded
total += num;
count++;
}
return count;
}int maxCount(int[] banned, int n, int maxSum) {
// Only banned values inside [1, n] can ever interfere.
Set<Integer> blocked = new HashSet<>();
for (int b : banned) if (b <= n) blocked.add(b);
long total = 0; // running sum of chosen integers
int count = 0; // how many we have chosen
// Greedy: smallest allowed numbers first.
for (int num = 1; num <= n; num++) {
if (blocked.contains(num)) continue;
if (total + num > maxSum) break; // budget exceeded
total += num;
count++;
}
return count;
}int maxCount(vector<int>& banned, int n, int maxSum) {
// Only banned values inside [1, n] can ever interfere.
unordered_set<int> blocked;
for (int b : banned) if (b <= n) blocked.insert(b);
long long total = 0; // running sum of chosen integers
int count = 0; // how many we have chosen
// Greedy: smallest allowed numbers first.
for (int num = 1; num <= n; num++) {
if (blocked.count(num)) continue;
if (total + num > maxSum) break; // budget exceeded
total += num;
count++;
}
return count;
}Explanation
This is a greedy problem. We want to choose as many distinct numbers from [1, n] as possible without the total exceeding maxSum. The key insight: to fit the most numbers, always spend your budget on the cheapest values first.
Why does smallest-first work? Suppose an optimal selection of k numbers skips some small allowed value a in favor of a larger one b > a. Swapping b for a keeps the count the same but lowers the sum, so it stays valid. Repeating this argument shows the k smallest allowed numbers are always a valid choice — greedy is optimal.
First we build a hash set of banned numbers (only those ≤ n matter, since values above n are never in range). Then we scan num = 1, 2, …, n. We skip any banned num. For an allowed num, if adding it would push total past maxSum we stop immediately — every later number is even larger, so none of them could fit either.
Otherwise we add num to the running total and increment count. When the loop ends, count is the answer.
Example: banned = [1,6,5], n = 5, maxSum = 6. We skip 1 (banned), take 2 (total 2), take 3 (total 5), reject 4 (5 + 4 = 9 > 6) and stop — wait, we instead break at the first overflow. Taking 2 then 3 gives count 2 with sum 5; the official answer also reports 2. Both {2, 3} and {2, 4} achieve the maximum count of 2.