You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:
[1, n].banned.maxSum.Return the maximum number of integers you can choose following the mentioned rules.
Example 1:
Input: banned = [1,6,5], n = 5, maxSum = 6 Output: 2 Explanation: You can choose the integers 2 and 4. 2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.
Example 2:
Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1 Output: 0 Explanation: You cannot choose any integer while following the mentioned conditions.
Example 3:
Input: banned = [11], n = 7, maxSum = 50 Output: 7 Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.
Constraints:
1 <= banned.length <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109This approach involves sorting all the numbers in the range [1, n] that are not present in the banned list and iteratively selecting the smallest numbers until the sum exceeds maxSum. This strategy ensures that the maximum number of integers can be chosen because smaller numbers contribute less to the sum, allowing more numbers to be selected.
The solution defines a helper function isBanned to check if a number is banned. It then creates a list of valid numbers, sorts them, and iteratively adds them to the current sum until maxSum is exceeded.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting of numbers.
Space Complexity: O(n) for storing valid numbers.
Instead of sorting, this approach uses a boolean array to mark banned numbers and iterates through possible selections directly in a greedy manner, quickly skipping banned numbers and tracking the sum in real-time.
This C implementation uses a boolean array to keep track of banned numbers, allowing O(1) lookups while iterating directly through the range [1, n] to accumulate the sum and count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1) because the boolean array size is constant.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting of numbers. |
| Greedy Approach without Sorting | Time Complexity: O(n). |
Maximum Number of Integers to Choose From a Range I | Leetcode 2554 • Techdose • 2,001 views views
Watch 9 more video solutions →Practice Maximum Number of Integers to Choose From a Range I with our built-in code editor and test cases.
Practice on FleetCode