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

Difficulty	Medium
Source	Daily-Question (POTD 06-Dec)
Tags	Array Hash Table Binary Search Greedy Sorting

🚀 2554 - Maximum Number of Integers to Choose From a Range I 🧠

Problem Link:

LeetCode - Maximum Number of Integers to Choose From a Range I

💡 Problem Breakdown:

You are given:

• An integer array banned that lists integers you cannot choose.
• Two integers n and maxSum.

You need to select integers from the range [1, n] following these rules:

1. Each integer can be selected at most once.
2. No selected integer can be in the banned array.
3. The sum of all selected integers must not exceed maxSum.

Objective:
Return the maximum number of integers you can select while following these rules.

🔍 Example Walkthrough:

Example 1:

Input:
banned = [1,6,5], n = 5, maxSum = 6
Output:
2
Explanation:

• Possible integers to choose: [2, 3, 4] (after excluding 1, 5, 6).
• Select 2 and 4. Their sum is 6, which meets the maxSum constraint.

Example 2:

Input:
banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output:
0
Explanation:

• No integers can be chosen because either they are banned or their sum exceeds maxSum.

Example 3:

Input:
banned = [11], n = 7, maxSum = 50
Output:
7
Explanation:

• Integers [1, 2, 3, 4, 5, 6, 7] are not banned, and their sum is 28, which is within maxSum. All 7 integers can be chosen.

🎯 My Approach:

1. Filter Valid Integers:

   • Remove integers from the range [1, n] that are present in the banned array.

2. Sort and Select:

   • Sort the remaining integers in ascending order.
   • Start picking integers one by one until their cumulative sum exceeds maxSum.

3. Early Stopping:

   • Stop as soon as adding the next integer exceeds maxSum to ensure efficiency.

🕒 Time Complexity:

• Filtering Banned Numbers:

  • Use a set to store banned numbers, allowing O(1) lookups.
  • Iterate through [1, n], resulting in O(n).

• Sorting Valid Integers:

  • Sort the valid integers, taking O(k log k) where k is the number of valid integers.

• Selecting Integers:

  • Iterate over valid integers (at most O(k)).

Overall:
O(n + k log k), where k is the number of integers not in banned.

📝 Solution Code

Code (C):

int maxCount(int* banned, int bannedSize, int n, int maxSum) {
    bool hashSet[n + 1]; 
    memset(hashSet, 0, sizeof(hashSet));

    for (int i = 0; i < bannedSize; i++) {
        if (banned[i] <= n)
            hashSet[banned[i]] = true;
    }

    int ans = 0, sum = 0;

    for (int i = 1; i <= n; i++) {
        if (hashSet[i]) 
            continue;

        if (sum + i > maxSum)
            break;

        sum += i;
        ans++;
    }

    return ans;
}

Code (C++)

class Solution {
 public:
  int maxCount(vector<int>& banned, int n, int maxSum) {
    sort(banned.begin(), banned.end());  
    int ans = 0, sum = 0, bannedIndex = 0;

    for (int i = 1; i <= n; ++i) {
      while (bannedIndex < banned.size() && banned[bannedIndex] < i)
        ++bannedIndex;
      
      if (bannedIndex < banned.size() && banned[bannedIndex] == i)
        continue;

      if (sum + i > maxSum)
        break;

      sum += i;
      ++ans;
    }

    return ans;
  }
};

Code (Java)

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        HashSet<Integer> bannedSet = new HashSet<>();
        for (int b : banned) {
            if (b <= n)
                bannedSet.add(b);
        }

        int ans = 0, sum = 0;

        for (int i = 1; i <= n; i++) {
            if (bannedSet.contains(i))
                continue;

            if (sum + i > maxSum)
                break;

            sum += i;
            ans++;
        }

        return ans;
    }
}

Code (Python)

class Solution:
    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)  
        ans = 0
        total_sum = 0

        for i in range(1, n + 1):
            if i in banned_set:  
                continue

            if total_sum + i > maxSum:
                break

            total_sum += i
            ans += 1

        return ans

Code (Rust)

use std::collections::HashSet;

impl Solution {
    pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {
        let banned_set: HashSet<i32> = banned.into_iter().collect(); 
        let mut ans = 0;
        let mut sum = 0;

        for i in 1..=n {
            if banned_set.contains(&i) {
                continue;
            }

            if sum + i > max_sum {
                break;
            }

            sum += i;
            ans += 1;
        }

        ans
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!