-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1891 [M] Cutting Ribbons
Code with Senpai edited this page Sep 15, 2022
·
14 revisions
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.
footer