# 1891. Cutting Ribbons

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mk7Pnlg-j2JQR4goDwy%2F-Mk7QFCIoQra1m4y1Ebi%2Fimage.png?alt=media\&token=a5eb8a12-bdff-4605-b7bb-ae8877d50751)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mk7Pnlg-j2JQR4goDwy%2F-Mk7QI1lea4cAFLyTVmj%2Fimage.png?alt=media\&token=58cd1676-791e-42ed-b293-3624f6af1ea1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mk7Pnlg-j2JQR4goDwy%2F-Mk7QKaDs12NSkOGiupY%2Fimage.png?alt=media\&token=a064ccab-448b-4e7f-b227-c2c20965bb02)

## binary search

time: O(nlogn), getCount use O(n), inside binary search, so O(nlogn)

space: O(1)



range: 1\~ max ribbons len,&#x20;

optimized,  use  Math.min(end, sum/k)



notice edge case : sum < k

```
1. find range in 1~9
2. 
      [7,5,9], k = 4
      
      1+ (9-1)/2  = 5, len = 5
      
      3 < k, so abandon right
      right = mid = 5, 1~5
      
      1 + (5-1)/2 = 3
      
      6 >= k, so abandon left
      start = mid, 3~5
      
      3 + (5-3)/2 = 4
      
      4 >= k, so start = mid = 4, go out while
      
      at last choose start or end
      
      
   1 2 3 4 5 6  <= cut len
7  7 3 2 1 1
5  5 2 1 1 1
9  9 4 3 2 1
k 21 9 6 4 3  . so k(段數) = 3, choose len 5




      [5,7,9], k = 22

cant!
```

```java
class Solution {
    public int maxLength(int[] ribbons, int k) {
        int start = 1;
        int end = 0;
        long sum = 0; // 注意, sum 要 long, test data 很大
        for (int ribbon : ribbons) {
            end = Math.max(end, ribbon); // end just set to max ribbons' len
            sum += ribbon;
        }
        
        // if has this, the ans will be the best
        // end  = (int)Math.min(end, sum/k);
        // if (end < 1) { // edge case check same as sum < k return 0
        //     return 0;
        // }
        
        if (sum < k) { //notice this, edge case
            return 0;
        }
        
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (getCount(ribbons, mid) >= k) { // get more than k, means mid(len) can be larger
                start = mid;
            } else {
                end = mid;
            }
        }
        return getCount(ribbons, end) >= k ? end : start;
    }

    private int getCount(int[] ribbons, int len) {
        int count = 0;
        for (int ribbon : ribbons) {
            count += ribbon/len;
        }
        return count;
    }
    
}
```

因為如果 end 符合, 優先回 end , 因為答案要長一點的

```java
return getCount(ribbons, end) >= k ? end : start;
```
