सकारात्मक संख्याओं की सूची दी गई है जो रिबन की लंबाई दर्शाती है, और एक मान k। हम रिबन को जितनी बार चाहें काट सकते हैं, हमें सबसे बड़ी लंबाई r खोजनी है जिससे हम k रिबन लंबाई r के प्राप्त कर सकें। यदि ऐसा समाधान नहीं मिलता, तो -1 लौटाएं।
उदाहरण
इनपुट: ribbons = [1, 2, 5, 7, 15], k = 5
आउटपुट: 5
व्याख्या: हम आकार 15 के रिबन को लंबाई 5 के 3 टुकड़ों में काट सकते हैं। फिर आकार 7 के रिबन को आकार 2 और 5 में काटें। और एक रिबन आकार 5 का पहले से है, इसलिए हमें कुल 5 रिबन आकार 5 के मिलते हैं।
एल्गोरिदम (बाइनरी सर्च)
left := 0right := max(ribbons)- जब
left < right:mid := (left + right + 1) // 2- यदि
sum(ribbonLen // mid for ribbonLen in ribbons) >= k:left := mid - अन्यथा:
right := mid - 1
- यदि
leftशून्येतर है:leftलौटाएं - अन्यथा: -1 लौटाएं
Python कार्यान्वयन
def solve(ribbons, k):
left = 0
right = max(ribbons)
while left < right:
mid = (left + right + 1) // 2
if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
left = mid
else:
right = mid - 1
if left:
return left
return -1
ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k)) # आउटपुट: 5
इनपुट/आउटपुट
Input: [1, 2, 5, 7, 15], 5
Output: 5