Maximum number of groups entering a competition

Array Math Binary Search Greedy

68.5% acceptance

Feb 25, 2026

713

121

You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions: The sum of the grades of students in the ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last). The total number of students in the ith group is less than the total number of students in the (i + 1)th group, for all groups (except the last). Return the maximum number of groups that can be formed.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_groups(grades: Vec<i32>) -> i32 {
    let n = grades.len() as i64;
    let mut lo = 1i64;
    let mut hi = 1500i64;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if mid * (mid + 1) / 2 <= n { lo = mid; } else { hi = mid - 1; }
    }
    lo as i32
  }
}