# 1891. Cutting Ribbons

![](/files/-Mk7QFCIoQra1m4y1Ebi)

![](/files/-Mk7QI1lea4cAFLyTVmj)

![](/files/-Mk7QKaDs12NSkOGiupY)

## binary search

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

space: O(1)

range: 1\~ max ribbons len, 

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;
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/1891.-cutting-ribbons.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.