Leetcode 2554: Maximum Number of Integers to Choose From a Range I
You are given an array
banned consisting of integers, an integer n, and an integer maxSum. Your task is to return the maximum number of integers you can select from the range [1, n] such that none of them are in the banned list and their sum does not exceed maxSum.Problem
Approach
Steps
Complexity
Input: You are given an array `banned` containing integers, an integer `n` representing the upper limit of the range, and an integer `maxSum` representing the sum limit.
Example: banned = [3, 7, 5], n = 6, maxSum = 10
Constraints:
• 1 <= banned.length <= 10^4
• 1 <= banned[i], n <= 10^4
• 1 <= maxSum <= 10^9
Output: Return the maximum number of integers you can select from the range [1, n] without exceeding `maxSum` and ensuring none of them are in the `banned` array.
Example: 3
Constraints:
Goal: Maximize the count of integers selected from [1, n] under the given constraints.
Steps:
• 1. Loop through the range [1, n] and for each integer, check if it is in the banned list and if adding it would exceed maxSum.
• 2. If the integer is not in the banned list and does not exceed the sum limit, add it to the selection and update the remaining sum.
• 3. Stop the selection once the sum exceeds maxSum.
Goal: Ensure the solution works for both small and large inputs as described in the constraints.
Steps:
• 1 <= banned.length <= 10^4
• 1 <= banned[i], n <= 10^4
• 1 <= maxSum <= 10^9
Assumptions:
• The array `banned` does not contain duplicate values.
• All integers in the range [1, n] are distinct.
• Input: banned = [3, 7, 5], n = 6, maxSum = 10
• Explanation: You can choose integers 1, 2, and 6. The sum of 1 + 2 + 6 = 9, which is under the maxSum of 10.
• Input: banned = [1, 2, 3], n = 5, maxSum = 4
• Explanation: The only integer you can choose is 4 because all others are banned.
Approach: The goal is to select as many integers as possible from the range [1, n] while avoiding the banned integers and ensuring the sum does not exceed maxSum.
Observations:
• The problem is essentially a greedy problem where we need to pick the smallest numbers first to maximize the count of selected integers.
• We can iterate through the range [1, n] and keep adding integers that are not banned and do not cause the sum to exceed maxSum.
Steps:
• 1. Initialize a counter to keep track of the number of integers selected.
• 2. Use a set or unordered map to check if an integer is banned.
• 3. Loop through the range [1, n], checking if the integer is not banned and the sum remains under maxSum.
• 4. Stop once the sum exceeds maxSum and return the counter.
Empty Inputs:
• The array `banned` will always contain at least one element based on the constraints.
Large Inputs:
• Ensure the solution handles cases where `banned` is large (up to 10^4 elements).
Special Values:
• Consider cases where all integers in the range [1, n] are banned or the sum limit is too low to select any integer.
Constraints:
• The solution must efficiently handle inputs up to the largest constraint values.
int n;
unordered_map<int, bool> mp;
int maxCount(vector<int>& ban, int n, int mxS) {
// this->n = n;
for(int x: ban)
mp[x] = true;
// memset(memo, -1, sizeof(memo));
// memo.resize(n + 1);
// return dp(1, mxS);
int cnt = 0;
for(int i = 1; i < n + 1; i++) {
if(!mp.count(i) && mxS >= i) {
cnt++;
mxS -= i;
}
if(mxS < 0) break;
}
return cnt;
}
1 : Variable Initialization
int n;
Here, the integer 'n' is declared to represent the upper limit for the numbers that can be considered (from 1 to 'n').
2 : Data Structure Initialization
unordered_map<int, bool> mp;
An unordered map 'mp' is declared to store the numbers that are excluded (banned numbers). It maps each excluded number to 'true'.
3 : Function Definition
int maxCount(vector<int>& ban, int n, int mxS) {
This is the function definition for 'maxCount'. It takes a vector of banned numbers, 'ban', an integer 'n' representing the upper limit of the range, and an integer 'mxS' representing the maximum sum constraint.
4 : Initialize Excluded Numbers
for(int x: ban)
This loop iterates through each banned number in the 'ban' vector and adds it to the unordered map 'mp', marking it as excluded.
5 : Add to Exclusion Map
mp[x] = true;
This line adds the number 'x' from the 'ban' list to the unordered map 'mp' with a value of 'true', indicating it is a banned number.
6 : Variable Initialization
int cnt = 0;
A counter variable 'cnt' is initialized to 0. It will be used to count how many numbers can be included within the sum constraint 'mxS'.
7 : Loop Through Numbers
for(int i = 1; i < n + 1; i++) {
This loop iterates through numbers from 1 to 'n' and checks if they can be included, based on the conditions set by the problem.
8 : Condition Check: Excluded and Sum
if(!mp.count(i) && mxS >= i) {
This if-condition checks if the number 'i' is not in the 'mp' map (not banned) and if it fits within the remaining sum 'mxS'.
9 : Increment Counter
cnt++;
If the number 'i' is not banned and fits within the sum constraint, 'cnt' is incremented to reflect that the number is included.
10 : Update Remaining Sum
mxS -= i;
This line updates the remaining sum 'mxS' by subtracting the value of 'i', indicating that 'i' has been included.
11 : Break If Sum Is Exceeded
if(mxS < 0) break;
This checks if the remaining sum 'mxS' has become negative, indicating that no more numbers can be included. If true, the loop is terminated early.
12 : Return Result
return cnt;
The function returns 'cnt', the total count of numbers that were successfully included within the sum constraint 'mxS'.
Best Case: O(n), where n is the range size (since we must check every integer at least once).
Average Case: O(n), assuming a constant-time check for banned integers.
Worst Case: O(n), as we need to check up to n integers for each selection.
Description:
Best Case: O(1), if no banned integers are used or the solution does not need additional storage.
Worst Case: O(n), since we may store up to n integers in a set or map to check for banned integers.
Description: Space complexity is primarily determined by the storage used to track banned integers.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus