# Maximum Number of Groups Entering a Competition
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-groups-entering-a-competition)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-groups-entering-a-competition
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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_.

**Example 1:**

**Input:** grades = [10,6,12,7,3,5]
**Output:** 3
**Explanation:** The following is a possible way to form 3 groups of students:
- 1st group has the students with grades = [12]. Sum of grades: 12. Student count: 1
- 2nd group has the students with grades = [6,7]. Sum of grades: 6 + 7 = 13. Student count: 2
- 3rd group has the students with grades = [10,3,5]. Sum of grades: 10 + 3 + 5 = 18. Student count: 3
It can be shown that it is not possible to form more than 3 groups.

**Example 2:**

**Input:** grades = [8,8]
**Output:** 1
**Explanation:** We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.

**Constraints:**

* `1 <= grades.length <= 105`
* `1 <= grades[i] <= 105`

# Approaches
## Sorting and Greedy Grouping
This approach is based on the intuition that to satisfy the sum condition (`sum_i < sum_{i+1}`), we should assign students with lower grades to earlier groups and students with higher grades to later groups. By sorting the `grades` array first, we can guarantee that if we form groups with increasing sizes (`count_i < count_{i+1}`), the sum condition will also be met. After sorting, we can greedily determine the number of groups.
**Time:** O(n log n), dominated by the sorting of the `grades` array. The subsequent loop runs `O(sqrt(n))` times, which is less significant. · **Space:** O(log n) or O(n), depending on the space used by the sorting algorithm's implementation (e.g., for recursion stack or temporary arrays).
**Pros:** Conceptually simple and directly models the problem constraints after sorting.; Guaranteed to be correct.
**Cons:** Highly inefficient due to the unnecessary sorting step, which has a time complexity of `O(n log n)`.; The core logic of the problem does not depend on the actual grade values, making the sorting redundant.
### Explanation
The core idea is that if we sort the grades in non-decreasing order, any group formed from consecutive students will have a smaller sum than the next group of a larger size formed from the subsequent students. This is because the later group will have more students, and each of its students will have a grade greater than or equal to any student in the previous group.

The algorithm proceeds as follows:
1.  Sort the `grades` array.
2.  Greedily form groups of increasing size: 1, 2, 3, and so on.
3.  We keep track of the number of students used. We start by forming a group of size 1, then size 2, and so on, as long as we have enough students remaining.
4.  The total number of groups we can form this way is the maximum possible.

The sorting step is the bottleneck, making this approach less efficient than others that realize the grade values are irrelevant.

```java
import java.util.Arrays;

class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        // Sorting is done to satisfy the sum condition easily, but as we'll see
        // in other approaches, it's not strictly necessary to solve the problem.
        Arrays.sort(grades);
        
        int k = 0; // number of groups
        int studentsUsed = 0;
        int nextGroupSize = 1;
        
        while (studentsUsed + nextGroupSize <= n) {
            studentsUsed += nextGroupSize;
            k++;
            nextGroupSize++;
        }
        
        return k;
    }
}
```
### Algorithm
- Get the total number of students, `n`, from the length of the `grades` array.
- Sort the `grades` array in non-decreasing order. This step ensures that if we form groups with increasing sizes, the sum of grades will also be strictly increasing.
- Initialize `k = 0` (number of groups) and `studentsUsed = 0`.
- Iterate with `nextGroupSize` starting from 1.
- In each step, check if we have enough remaining students to form a group of this size, i.e., if `studentsUsed + nextGroupSize <= n`.
- If we do, it means we can form another group. Increment `k`, add `nextGroupSize` to `studentsUsed`, and increment `nextGroupSize` for the next iteration.
- If not, we don't have enough students, so we stop.
- Return `k` as the maximum number of groups.

## Iterative Simulation without Sorting
This approach realizes that the actual values of the grades do not matter, only the total number of students. The conditions on group sums can always be satisfied by sorting the grades and assigning the smallest ones to the first groups. Therefore, the problem reduces to a mathematical puzzle: find the maximum number of groups `k` such that we can partition `n` students into groups of strictly increasing sizes. To maximize `k`, we should use the smallest possible sizes: 1, 2, 3, ..., `k`.
**Time:** O(sqrt(n)). The loop runs `k` times, where `k` is the result. We know `k * (k + 1) / 2` is approximately `n`, so `k` is proportional to `sqrt(n)`. · **Space:** O(1), as we only use a few variables to keep track of the state.
**Pros:** More efficient than the sorting approach as it avoids the `O(n log n)` step.; Simple to implement and understand.; Uses constant extra space.
**Cons:** Not the most optimal solution, as logarithmic or constant time solutions exist.
### Explanation
The problem is to find the largest integer `k` such that the sum of the first `k` positive integers is less than or equal to the total number of students `n`. That is, `1 + 2 + ... + k <= n`.

We can simulate this process iteratively. We start with `k=0` groups and `n` students. In each step, we try to form a new group. The first group requires 1 student, the second requires 2, and so on. The `i`-th group requires `i` students.

We loop, subtracting the required number of students for the next group from our total `n`, and incrementing our group count, until we no longer have enough students.

```java
class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        int k = 0;
        int studentsNeeded = 1;
        while (n >= studentsNeeded) {
            n -= studentsNeeded;
            k++;
            studentsNeeded++;
        }
        return k;
    }
}
```
### Algorithm
- Get the total number of students, `n`.
- Initialize `k = 0` (number of groups) and `groupSize = 1`.
- Loop as long as the remaining students `n` are enough to form the next group of size `groupSize`.
- Inside the loop, subtract `groupSize` from `n` to account for the students used.
- Increment the group count `k`.
- Increment `groupSize` for the next iteration.
- When the loop terminates, `k` holds the maximum number of groups. Return `k`.

## Binary Search on the Number of Groups
This approach builds upon the insight from the iterative method. We are looking for the maximum integer `k` that satisfies the condition `1 + 2 + ... + k <= n`, which is equivalent to `k * (k + 1) / 2 <= n`. The function `f(k) = k * (k + 1) / 2` is monotonically increasing for `k > 0`. This property allows us to use binary search to find the answer `k` efficiently.
**Time:** O(log n). The binary search reduces the search space (from `0` to `n`) by half in each step. · **Space:** O(1), as the binary search is done in-place with a few variables.
**Pros:** Very efficient, significantly faster than linear or `O(sqrt(n))` approaches for large `n`.; Optimal time complexity among common algorithmic approaches (excluding a direct mathematical formula).
**Cons:** Slightly more complex to implement than the straightforward iterative approach.
### Explanation
We can binary search for the answer `k` in the range `[0, n]`. For a given `mid` value (a potential `k`), we can quickly check if it's possible to form `mid` groups.

The check involves calculating the minimum number of students required, which is `mid * (mid + 1) / 2`.
- If this required number is less than or equal to `n`, it means `mid` groups are possible, so we try for a larger `k` by moving our search to the right half (`low = mid + 1`). We also store `mid` as a potential answer.
- If the required number is greater than `n`, `mid` is too large, and we must try for a smaller `k` by moving our search to the left half (`high = mid - 1`).

The search continues until `low` crosses `high`, and the last valid `mid` we found is our answer.

```java
class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        long low = 0, high = n;
        long ans = 0;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            // Students needed for 'mid' groups
            long studentsNeeded = mid * (mid + 1) / 2;
            
            if (studentsNeeded <= n) {
                // 'mid' is a possible answer, try for more groups
                ans = mid;
                low = mid + 1;
            } else {
                // 'mid' is too large, try for fewer groups
                high = mid - 1;
            }
        }
        return (int)ans;
    }
}
```
### Algorithm
- Get the total number of students, `n`.
- Initialize search boundaries `low = 0`, `high = n`.
- Initialize `ans = 0` to store the result.
- While `low <= high`:
    - a. Calculate `mid = low + (high - low) / 2`.
    - b. Calculate students needed for `mid` groups: `needed = (long)mid * (mid + 1) / 2`. Use `long` to prevent overflow.
    - c. If `needed <= n`: `mid` is a valid number of groups. Store it in `ans` and search for a larger `k` by setting `low = mid + 1`.
    - d. If `needed > n`: `mid` is too large. Search for a smaller `k` by setting `high = mid - 1`.
- Return `ans`.

## Constant Time Mathematical Solution
This is the most optimal approach. It directly calculates the result using a mathematical formula derived from the core inequality `k * (k + 1) / 2 <= n`. By solving this quadratic inequality for `k`, we can find the answer in constant time.
**Time:** O(1). The calculation involves a few arithmetic operations and a square root, which are considered constant time operations. · **Space:** O(1), as it only involves a few calculations with no extra data structures.
**Pros:** The most efficient solution possible with constant time complexity.; Elegant and concise implementation.
**Cons:** Requires mathematical insight to derive the formula, which might not be immediately obvious during a contest or interview.
### Explanation
The problem is to find the largest integer `k` satisfying `k * (k + 1) / 2 <= n`.
This can be rewritten as a quadratic inequality: `k^2 + k - 2n <= 0`.
To find the range of `k` that satisfies this, we first find the roots of the corresponding equation `k^2 + k - 2n = 0`.
Using the quadratic formula, `k = (-b ± sqrt(b^2 - 4ac)) / 2a`, with `a=1, b=1, c=-2n`, the positive root is `k = (-1 + sqrt(1 + 8n)) / 2`.
Since we are looking for the largest *integer* `k` that satisfies the inequality, the answer is the floor of this value. This gives us a direct formula to compute the result.

```java
class Solution {
    public int maximumGroups(int[] grades) {
        int n = grades.length;
        // We need to find the largest k such that k * (k + 1) / 2 <= n.
        // This is equivalent to k^2 + k - 2n <= 0.
        // Solving k^2 + k - 2n = 0 for k gives the positive root:
        // k = (-1 + sqrt(1 + 8n)) / 2
        // The answer is the floor of this value.
        double k = (Math.sqrt(1 + 8.0 * n) - 1) / 2.0;
        return (int) k;
    }
}
```
### Algorithm
- Get the total number of students, `n`.
- Apply the formula derived from the quadratic inequality: `k = (sqrt(1 + 8n) - 1) / 2`.
- Since `k` must be an integer representing the number of full groups, take the floor of the result.
- Return the resulting integer value of `k`.

# Solutions
### Java

```java
class Solution {
public
  int maximumGroups(int[] grades) {
    int n = grades.length;
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (1L * mid * mid + mid > n * 2L) {
        r = mid - 1;
      } else {
        l = mid;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution { public: int maximumGroups ( vector < int >& grades ) { int n = grades . size (); int l = 0 , r = n ; while ( l < r ) { int mid = ( l + r + 1 ) >> 1 ; if ( 1LL * mid * mid + mid > n * 2LL ) { r = mid - 1 ; } else { l = mid ; } } return l ; } };
```

### Python

```python
class Solution:
    def maximumGroups(self, grades: List[int]) -> int: n = len(grades) return bisect_right(range(n + 1), n * 2, key=lambda x: x * x + x) - 1

```