Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2358.html
2358. Maximum Number of Groups Entering a Competition
 Difficulty: Medium.
 Related Topics: Array, Math, Binary Search, Greedy.
 Similar Questions: Maximum Height by Stacking Cuboids .
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 nonempty 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
Solution (Java, C++, Python)

class Solution { public int maximumGroups(int[] grades) { int len = grades.length; return (int) (1 + Math.sqrt(1D + 8 * len)) / 2; } } ############ 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; } }

class Solution: def maximumGroups(self, grades: List[int]) > int: grades.sort() ans = 1 prev = [1, grades[0]] curr = [0, 0] for v in grades[1:]: curr[0] += 1 curr[1] += v if prev[0] < curr[0] and prev[1] < curr[1]: prev = curr curr = [0, 0] ans += 1 return ans ############ # 2358. Maximum Number of Groups Entering a Competition # https://leetcode.com/problems/maximumnumberofgroupsenteringacompetition/ class Solution: def maximumGroups(self, grades: List[int]) > int: n = len(grades) res = 1 currSize = 0 size = 2 for i in range(1, n): currSize += 1 if currSize == size: res = currSize size += 1 currSize = 0 return res

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; } };

func maximumGroups(grades []int) int { n := len(grades) return sort.Search(n, func(k int) bool { k++ return k*k+k > n*2 }) }

function maximumGroups(grades: number[]): number { const n = grades.length; let l = 1; let r = n; while (l < r) { const mid = (l + r + 1) >> 1; if (mid * mid + mid > n * 2) { r = mid  1; } else { l = mid; } } return l; }
Explain:
nope.
Complexity:
 Time complexity : O(n).
 Space complexity : O(n).