2554. Maximum Number of Integers to Choose From a Range I
Problem Description
The problem presents a task involving selection from a range of integers while adhering to certain constraints:
- You have to choose integers from a range between 1 and
n
(inclusive). - Each integer in the range can be chosen at most once.
- There is a given list of banned integers (
banned
), which you cannot choose. - The sum of the chosen integers cannot exceed a specified sum (
maxSum
).
Your goal is to select the maximum number of integers possible without violating any of the above rules. The result that needs to be returned is the count of such integers.
Intuition
To solve this problem, a greedy approach can be utilized. The intuition here is that to maximize the number of integers to select, one should start from the smallest possible integer and move up, because smaller integers add less to the total sum, thus allowing for more integers to be included without exceeding maxSum
.
Here are the steps for the given greedy approach:
- Initialize a counter (
ans
) to keep track of the count of integers chosen and a sum (s
) to keep track of the sum of chosen integers. - Create a set (
ban
) from thebanned
list for efficient lookup of banned integers. - Start iterating over the integers in the range from 1 to
n
inclusive. - For each integer:
- Check if adding this integer to the current sum (
s
) would exceedmaxSum
. If it would, break out of the loop as no more integers can be chosen without violating the sum constraint. - Check if the integer is not in the
ban
set. If the integer is not banned, increment the count (ans
) by 1 and add the integer to the sum (s
).
- Check if adding this integer to the current sum (
- Return the count (
ans
) as the final answer.
By following this approach, each decision contributes to the overall objective of maximizing the count by choosing the smallest non-banned integers first, while also ensuring the total sum does not go over maxSum
.
Learn more about Greedy, Binary Search and Sorting patterns.
Solution Approach
The implementation of the solution in Python follows the steps outlined in the intuition.
Here's a step-by-step explanation of the code provided in the Reference Solution Approach, referring to the algorithm and data structures used:
-
Initialize two variables:
ans
to store the running count of chosen numbers, initially set to 0.s
to store the current sum of chosen numbers, also initially set to 0.
-
Convert the
banned
list of integers into a set calledban
. A set is used because it provides O(1) time complexity for checking if an item exists in it, which is far more efficient than using a list, especially when thebanned
list is large. -
Iterate over the integers from 1 to
n
inclusive using a for loop. This is the range from which you can choose the integers. -
In each iteration, perform two checks before choosing an integer:
- If the current sum
s
plus the current integeri
is greater thanmaxSum
, terminate the loop. This check ensures that the solution doesn't exceed the allowed sum constraint. - If the current integer
i
is not in theban
set, incrementans
by 1 and addi
to the sums
. This action effectively chooses the integer and updates the count and sum accordingly.
- If the current sum
-
Once the loop ends (either by exceeding
maxSum
or after checking all possible integers), returnans
. This final value represents the maximum number of integers you can choose that satisfy the given constraints.
This algorithm is an efficient way to solve the problem because it works incrementally to build the solution, ensuring at each step that the conditions are met. By starting from the smallest possible number and moving up, it adheres to the greedy approach strategy, which in this case is optimal.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we have n = 10
, banned = [3, 5, 7]
, and maxSum = 15
.
-
Initialize
ans = 0
and sums = 0
. -
Convert the banned list into a set:
ban = {3, 5, 7}
. -
Start iterating from
i = 1
ton = 10
.- For
i = 1
:s + i = 1
<=maxSum = 15
, and1
is not inban
. So,ans = 1
ands = 1
. - For
i = 2
:s + i = 3
<=maxSum
, and2
is not inban
. Nowans = 2
ands = 3
. - For
i = 3
: Skip since3
is inban
. - For
i = 4
:s + i = 7
<=maxSum
, and4
is not inban
. Updateans = 3
ands = 7
. - For
i = 5
: Skip since5
is inban
. - For
i = 6
:s + i = 13
<=maxSum
, and6
is not inban
. Updateans = 4
ands = 13
. - For
i = 7
: Skip since7
is inban
. - For
i = 8
:s + i = 21
>maxSum
, so we break the loop as adding8
would exceedmaxSum
.
- For
-
Having completed the iteration or stopped when we could no longer add integers without exceeding
maxSum
, we have a finalans = 4
.
This walk-through illustrates how the algorithm makes choices and updates both the number of integers chosen and the current sum while respecting the constraints. The value of ans
after the loop ends (in this case, 4
) is the number we would return as the maximum count of integers we can choose within the rules.
Solution Implementation
1class Solution:
2 def maxCount(self, banned_numbers: List[int], n: int, max_sum: int) -> int:
3 count = 0 # Initialize the count of numbers that aren't banned and whose sum is within max_sum
4 current_sum = 0 # Initialize the current sum of numbers
5 banned_set = set(banned_numbers) # Convert the banned list to a set for faster lookups
6
7 # Iterate through the numbers from 1 to n
8 for i in range(1, n + 1):
9 # Check if adding the current number would exceed the maximum allowed sum
10 if current_sum + i > max_sum:
11 break # If it would, break out of the loop early
12
13 # Check if the current number is not banned
14 if i not in banned_set:
15 count += 1 # Increment the count of valid numbers
16 current_sum += i # Add the current number to the sum
17
18 # Return the final count of valid numbers
19 return count
20
1class Solution {
2 // Method that returns the maximum count of distinct integers that can be chosen
3 // from 1 to n such that their sum does not exceed maxSum and they are not in the banned list
4 public int maxCount(int[] bannedNumbers, int n, int maxAllowedSum) {
5 // Create a hash set to store the banned numbers for easy access
6 Set<Integer> bannedSet = new HashSet<>(bannedNumbers.length);
7
8 // Populate the bannedSet with numbers from the bannedNumbers array
9 for (int number : bannedNumbers) {
10 bannedSet.add(number);
11 }
12
13 // Initialize answer to store the count of possible numbers and sum to track current sum
14 int count = 0;
15 int currentSum = 0;
16
17 // Iterate through integers from 1 to n
18 for (int i = 1; i <= n && currentSum + i <= maxAllowedSum; ++i) {
19 // If the current number is not in the banned set
20 if (!bannedSet.contains(i)) {
21 // Increment the answer count and add the number to the current sum
22 ++count;
23 currentSum += i;
24 }
25 }
26
27 // After the loop, return the total count of selectable numbers that meet the criteria
28 return count;
29 }
30}
31
1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7 // Function to calculate the maximum number of unique integers we can sum up
8 // to maxSum without including any integers from the banned list.
9 // Parameters:
10 // - banned - a list of integers to be excluded
11 // - n - the range of positive integers to consider (1 to n)
12 // - maxSum - the maximum allowable sum
13 // Returns the maximum count of unique integers within the limit of maxSum, excluding banned ones.
14 int maxCount(vector<int>& banned, int n, int maxSum) {
15 // Convert the vector of banned numbers into an unordered_set for efficient lookup
16 unordered_set<int> bannedNumbers(banned.begin(), banned.end());
17
18 // Initialize a counter for the answer and a variable to keep the current sum
19 int answer = 0;
20 int currentSum = 0;
21
22 // Iterate through the numbers from 1 to n
23 for (int i = 1; i <= n && currentSum + i <= maxSum; ++i) {
24 // Check if the current number is not in the banned set
25 if (!bannedNumbers.count(i)) {
26 // Increment the count of usable numbers
27 ++answer;
28 // Add the current number to the running sum
29 currentSum += i;
30 }
31 }
32 // Return the maximum count of unique integers found that we can sum up to maxSum
33 return answer;
34 }
35};
36
1function maxCount(banned: number[], n: number, maxSum: number): number {
2 // Create a Set from the banned array to facilitate O(1) look-up times.
3 const bannedSet = new Set(banned);
4
5 // Initialize sum to keep track of the total sum of non-banned numbers.
6 let sum = 0;
7
8 // Initialize ans to keep track of the count of numbers that can be added without exceeding maxSum.
9 let ans = 0;
10
11 // Iterate through numbers from 1 to n.
12 for (let i = 1; i <= n; i++) {
13 // If adding the current number exceeds maxSum, exit the loop.
14 if (i + sum > maxSum) {
15 break;
16 }
17
18 // If the current number is in the banned set, skip to the next iteration.
19 if (bannedSet.has(i)) {
20 continue;
21 }
22
23 // Add the current non-banned number to the sum.
24 sum += i;
25
26 // Increment the count since we have successfully added a non-banned number without exceeding maxSum.
27 ans++;
28 }
29
30 // Return the count of non-banned numbers added without exceeding maxSum.
31 return ans;
32}
33
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
is the input parameter that defines the range of numbers we are considering (1
to n
). This is because the code iterates over each number from 1
to n
at most once. During each iteration, the algorithm performs a constant-time operation: checking if the number is not in the banned set and if adding the current number would exceed maxSum
. If neither condition is true, it performs two additional constant-time operations: incrementing ans
and adding the number to the running total s
.
The space complexity of the code is O(b)
, where b
is the length of the banned
list. This accounts for the space needed to store the banned numbers in a set for quick lookup.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!