aboutsummaryrefslogtreecommitdiff
path: root/max_num_group_entre_comp.c
blob: 48ec41d2e87650a04a09bcd7fd4506dfac08cfa5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 2358. Maximum Number of Groups Entering a Competition
#include "leetcode.h"
/*
 * given a positive integer array 'grades' which represents the grades of
 * students in a university. you would like to entre all these students into a
 * competition in orderd non empty groups such that the ordering meets the
 * following requirements. the sum of the grades of students in the i'th group
 * is less than the sum of the grades of students in the '(i +1)'th group for
 * all groups except last. the total number of students in the i'th group is
 * less than the total number of students in the i'th group is less than the
 * gtotal numboer of students in the '(i + 1)'th group, for all groups. return
 * the maximum numberof groups that can be formed.
 */

int maximumGroups(int *grades, int gradesSize) {
  int left = 1, right = gradesSize / 2 + 1, mid, sum;
  while (left < right) {
    mid = right - (right - left) / 2;
    sum = (1 + mid) * mid / 2;
    if (sum == gradesSize)
      return mid;
    if (sum > gradesSize)
      right = mid - 1;
    else
      left = mid;
    ;
  }
  return left;
}

int main() {
  int g1[] = {10, 6, 12, 7, 3, 5}, g2[] = {8, 8};
  printf("%d\n", maximumGroups(g1, ARRAY_SIZE(g1))); // expect: 3
  printf("%d\n", maximumGroups(g2, ARRAY_SIZE(g2))); // expect: 1
}