aboutsummaryrefslogtreecommitdiff
path: root/koko_eating_bananas.c
blob: 4d0d0cd85938895879ca6f379a0f5972ad48c0fd (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
// 875. Koko Eating Bananas
#include <stdio.h>

// return minimum integer 'k' such that koko can eat all bananas within 'h'
// hours

int minEatingSpeed(int *piles, int piles_size, int h) {
  int l = 1, r = 1000000000;
  while (l < r) {
    int m = (l + r) / 2, total = 0;
    for (int i = 0; i < piles_size; i++)
      total += (piles[i] + m - 1) / m;
    if (total > h)
      l = m + 1;
    else
      r = m;
  }
  return l;
}

int main() {
  int p1[] = {3, 6, 7, 11}, p2_3[] = {30, 11, 23, 4, 20};
  printf("%d\n", minEatingSpeed(p1, sizeof(p1) / sizeof(p1[0]), 8)); // expect:
                                                                     // 4
  printf("%d\n",
         minEatingSpeed(p2_3, sizeof(p2_3) / sizeof(p2_3[0]), 5)); // expect: 30
  printf("%d\n",
         minEatingSpeed(p2_3, sizeof(p2_3) / sizeof(p2_3[0]), 6)); // expect: 23
}