875. Koko Eating Bananas

Binary search

T:O(n + plogp) - p is piles value, n is piles length
S:O(1)

```java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        while (left < right) {
            int mid = left + (right - left)/2;
            int count = 0;
            for (int pile : piles) {
                if (mid == 0) {
                    return left;
                } else {
                    count += pile/mid + (pile%mid != 0 ? 1 : 0);
                }
            }
            if (count <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

/*
Binary search
T:O(n + plogp) - p is piles value, n is piles length
S:O(1)


piles = [3,6,7,11], h = 8

h = 8

3, 6, 7, 11
1 2.  2. 3

32

piles[i]/k + (piles[i]%k != 0 ? 1 : 0)


*/
```

new version

```java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int right = 0;
        int left = 1;
        int test = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
            test += pile;
        }
        while (left <= right) {
            int mid = left + (right - left)/2;
            long hours = getHour(piles, mid);
            
            if (hours < h) {
                right = mid - 1;
            } else if (hours > h){
                left = mid + 1;
            } else {
                if (mid-1 >= 0 && getHour(piles, mid-1) == h) {
                    right = mid - 1; 
                } else {
                    return mid;
                }
            }
        }
        return left;
    }
    // for new test case: piles = [805306368,805306368,805306368]
    // h = 1000000000
    // getHour with int will become negative, so use long to add
    long getHour(int[] piles, int mid) {
        long hours = 0;
        for (int pile : piles) {
            hours += ((long)pile/mid + (pile%mid != 0 ? 1 : 0));
        }
        return hours;
    }
}

/*
h = 8
3 6 7 11
6
1.1 2. 2 < 8

hour and k is relatively

3~11

3+11)/2 = 7

3 7 -> 5
3 5
8/2 = 4

3 4
7/2 = 3

3 6 7 11
1 2 2 3

1 2 3 4 -> over h = 8
*/
```