Maximum number of integers to choose from a range ii

Array Binary Search Greedy Sorting

34.9% acceptance

Mar 31, 2026

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules: The chosen integers have to be in the range [1, n]. Each integer can be chosen at most once. The chosen integers should not be in the array banned. The sum of the chosen integers should not exceed maxSum. Return the maximum number of integers you can choose following the mentioned rules.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i64) -> i32 {
    let mut banned: Vec<i64> = banned.into_iter().map(|x| x as i64).collect();
    banned.sort();
    banned.dedup();
    let n = n as i64;
    let mut count = 0i32;
    let mut current_sum = 0i64;
    let mut prev = 0i64; // last number we processed
    for &b in &banned {
      if b > n { break; }
      // Numbers from prev+1 to b-1 are available
      let lo = prev + 1;
      let hi = b - 1;
      if lo <= hi {
        // Binary search for how many we can take from [lo, hi]
        // Sum of lo..=lo+k-1 = k*lo + k*(k-1)/2
        let range_len = hi - lo + 1;
        let mut left = 0i64;
        let mut right = range_len;
        while left < right {
          let mid = (left + right + 1) / 2;
          let s = mid * lo + mid * (mid - 1) / 2;
          if current_sum + s <= max_sum {
            left = mid;
          } else {
            right = mid - 1;
          }
        }
        current_sum += left * lo + left * (left - 1) / 2;
        count += left as i32;
      }
      prev = b;
    }
    // Numbers from prev+1 to n
    let lo = prev + 1;
    let hi = n;
    if lo <= hi {
      let range_len = hi - lo + 1;
      let mut left = 0i64;
      let mut right = range_len;
      while left < right {
        let mid = (left + right + 1) / 2;
        let s = mid * lo + mid * (mid - 1) / 2;
        if current_sum + s <= max_sum {
          left = mid;
        } else {
          right = mid - 1;
        }
      }
      current_sum += left * lo + left * (left - 1) / 2;
      count += left as i32;
    }
    count
  }
}