2554. Maximum Number of Integers to Choose From a Range I

MediumGreedyArrayHash TableBinary SearchSorting
Leetcode Link

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:

  1. 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.
  2. Create a set (ban) from the banned list for efficient lookup of banned integers.
  3. Start iterating over the integers in the range from 1 to n inclusive.
  4. For each integer:
    • Check if adding this integer to the current sum (s) would exceed maxSum. 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).
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which data structure is used in a depth first search?

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:

  1. 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.

  2. Convert the banned list of integers into a set called ban. 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 the banned list is large.

  3. Iterate over the integers from 1 to n inclusive using a for loop. This is the range from which you can choose the integers.

  4. In each iteration, perform two checks before choosing an integer:

    • If the current sum s plus the current integer i is greater than maxSum, terminate the loop. This check ensures that the solution doesn't exceed the allowed sum constraint.
    • If the current integer i is not in the ban set, increment ans by 1 and add i to the sum s. This action effectively chooses the integer and updates the count and sum accordingly.

  5. Once the loop ends (either by exceeding maxSum or after checking all possible integers), return ans. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example 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.

  1. Initialize ans = 0 and sum s = 0.

  2. Convert the banned list into a set: ban = {3, 5, 7}.

  3. Start iterating from i = 1 to n = 10.

    • For i = 1: s + i = 1 <= maxSum = 15, and 1 is not in ban. So, ans = 1 and s = 1.
    • For i = 2: s + i = 3 <= maxSum, and 2 is not in ban. Now ans = 2 and s = 3.
    • For i = 3: Skip since 3 is in ban.
    • For i = 4: s + i = 7 <= maxSum, and 4 is not in ban. Update ans = 3 and s = 7.
    • For i = 5: Skip since 5 is in ban.
    • For i = 6: s + i = 13 <= maxSum, and 6 is not in ban. Update ans = 4 and s = 13.
    • For i = 7: Skip since 7 is in ban.
    • For i = 8: s + i = 21 > maxSum, so we break the loop as adding 8 would exceed maxSum.

  4. Having completed the iteration or stopped when we could no longer add integers without exceeding maxSum, we have a final ans = 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Binary Search Speedrun

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

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ