রিবনের দৈর্ঘ্যের তালিকা (ribbons) এবং একটি মান k দেওয়া আছে। রিবনগুলো যেকোনো সংখ্যক বার কাটা যায়। এমন সর্বোচ্চ দৈর্ঘ্য r বের করতে হবে যাতে কমপক্ষে kটি r দৈর্ঘ্যের রিবন পাওয়া যায়। না পেলে -1 রিটার্ন করুন।
সমস্যা উদাহরণ
ইনপুট: ribbons = [1, 2, 5, 7, 15], k = 5
আউটপুট: 5
ব্যাখ্যা: ১৫ কেটে ৫+৫+৫ (৩টি), ৭ কেটে ৫+২ (১টি), ৫ (১টি) = মোট ৫টি ৫ দৈর্ঘ্যের রিবন।
সমাধানের পদ্ধতি (বাইনারি সার্চ)
left = 0,right = max(ribbons)- যখন
left < right:mid = (left + right + 1) // 2(উপরের মিড)- যদি
sum(ribbonLen // mid for ribbonLen in ribbons) >= kহলেleft = mid - অন্যথায়
right = mid - 1
- যদি
left != 0হলেleftরিটার্ন করুন, অন্যথায় -1
পাইথন কোড
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টেস্ট কেস
ইনপুট: [1, 2, 5, 7, 15], 5
আউটপুট: 5
সময় জটিলতা: O(n log M) যেখানে M = max(ribbons)।
