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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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.

Solution

Method 1 - Using Iterative Formula

First, sort all the grades. Then, assign 1 student to the first group, 2 students to the second group, and so on. This ensures that the i-th group is smaller in size and sum compared to the (i+1)-th group.

To determine the maximum possible k such that 1 + 2 + ... + k <= n:

Proof: When we sort the groups by size, the first group must have at least 1 student, the second group at least 2 students, and the k-th group at least k students.

This demonstrates the upper limit of k, and I have provided a method to achieve this arrangement.

Code

1
2
3
4
5
6
7
8

public int maximumGroups(int[] grades) {
	int k = 0, total = 0, n = grades.length;
	while (total + k + 1<= n) {
		k++;
		total += k;
	}
	return k;
}

Complexity

  • ⏰ Time complexity: O(sqrt(n))
  • 🧺 Space complexity: O(1)

Method 2 - Using Binary Search

To find the largest k such that 1 + 2 + ... + k <= n, solve the inequality k(k + 1) / 2 <= n. We can use binary search to determine the maximum k that satisfies k(k + 1) / 2 <= n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public int maximumGroups(int[] A) {
	int left = 0, right = 1000, n = A.length;
	while (left < right) {
		int k = (left + right + 1) / 2;
		if (k * (k + 1) / 2 > n) {
			right = k - 1;
		} else {
			left = k;
		}
	}
	return left;
}

Complexity

  • ⏰ Time complexity: O(log 1000)
  • 🧺 Space complexity: O(1)

Method 3 - Using Mathematical Formula

Given 1 + 2 + ... + k <= n, we derive that k(k + 1) / 2 <= n. This can be rewritten as (k + 0.5)^2 <= 2n + 0.25. Taking the square root on both sides, we get k + 0.5 <= sqrt(2n + 0.25). Finally, solving for k, we find k <= sqrt(2n + 0.25) - 0.5.

1
2
3
4
5

1 + 2 + ... + k <= n
k(k + 1) / 2 <= n
(k + 0.5)(k + 0.5) <= n * 2 + 0.25
k + 0.5 <= sqrt(n * 2 + 0.25)
k <= sqrt(n * 2 + 0.25) - 0.5

Code

1
2
3

public int maximumGroups(int[] A) {
	return (int)(Math.sqrt(A.length * 2 + 0.25) - 0.5);
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)