LC 1891 [M] Cutting Ribbons - ALawliet/algorithms GitHub Wiki

this has weird case cases for r and return l - 1

Your goal is to obtain k ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting.

Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length

class Solution(object):
    def maxLength(self, ribbons: List[int], k: int) -> int:
            if sum(ribbons) < k: return 0 # not possible even if we cut in 1 
            
            l = 1
            r = max(ribbons) + 1 # + 1 for the stupid 99999->100000 edge case
            
            while l < r: 
                m = (l + r) // 2
                cuts = sum([x // m for x in ribbons]) # just a basic for loop adding them up 
                if not cuts < k: # too many cuts, we need bigger cuts
                    l = m + 1
                else: # too little cuts, we need smaller cuts
                    r = m
            return l - 1 # because we start l and r +1

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        # The minumum length of the ribbon that we can cut is 1
        start = 1
        # The maximum length of the ribbon can be the maximum element in the list
        end = max(ribbons)
        
        # In this binary search, we are trying to go through the origin list and figure out which integer(from 1 -> ribbon of max length) is the deired length for the the target k pieces
        while(start <= end):
            mid = (start + end) // 2 # cut size
            res = 0
            for i in ribbons: # try to cut each ribbon by the cut size
                res += i // mid # num ribbons
            # If the value is >= target, we know that there could be a larger integer that will satisfy the same conditon
            if res >= k:
                start = mid+1
            else:
            # If lesser than k, then there could be a value lesser than the mid that could satisfy the condition
                end = mid -1
        return end # end must be < start, so we return this for the optimal cut, start would be bigger than the correct solution

So when the loop exits, you know that end will be less than start. That's what I observed with this binary search template too.
Yes, to expand more, I thought about this as - the while loop's condition is start <= end. So when the loop exits, you know that end will be less than start. We want to return the smaller value to ensure that you are cutting the ribbons as close to the optimal length as possible, but definitely not longer (since then you won't get a valid cut and achieve k pieces).

class Solution:
    def maxLength(self, ribbons: List[int], k: int) -> int:
        total = sum(ribbons)
        if k > total:
            return 0
        
        lo, hi = 1, min(total // k, max(ribbons))
        
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if sum(x // mid for x in ribbons) >= k:
                lo = mid
            else:
                hi = mid - 1
        
        return lo

The trick lies in the fact that when lo = hi - 1 and the value >= k, we will stuck in low = mid, i.e. an infinite loop.

However, with (lo + hi + 1) // 2, no matter it is >= k or < k, we don't have infinite loop. And also (lo + hi + 1) // 2 and (lo + hi) // 2 both returns the middle number with no difference regarding the binary search itself.

think about when you have only 2 elements left to compare to e.g. [5,3] where 5 and 3 represent total possible ribbons that can be achieved for some consecutive numbers. If k = 4, you would want the result to be the num of 5 because 3 ribbons won't cut it (pun intended). So you compare the higher number (+1) and then set hi = mid-1, which will leave you with 5.

If you write the binary search as

while l < r:
	m = l + (r - l) // 2
	if self.can_cut_k_ribbons_with_length_x(ribbons, k, m):
		l = m
	else:
		r = m - 1
return l

because we start l = 1, When r - l == 1, the loop will be stuck. The solution is to change the condition to l <= r, l = m + 1. When you exit the loop, l will be one larger than r. You can simply return the r or l - 1.