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

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/maximum-number-of-groups-entering-a-competition/
    
    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).

All Problems

All Solutions