পাইথনে ক্ষুদ্রতম গ্রুপের সর্বোচ্চ সম্ভাব্য মান খুঁজে বের করার প্রোগ্রাম

মনে করুন আমাদের একটি সংখ্যার তালিকা nums এবং আরেকটি মান k আছে। আমাদের তালিকাটিকে k টি সन्नিহিত গ্রুপে ভাগ করতে হবে। ক্ষুদ্রতম গ্রুপ হলো যার সমষ্টি সব গ্রুপের মধ্যে সর্বনিম্ন। তাই ক্ষুদ্রতম গ্রুপের সর্বোচ্চ সম্ভাব্য মান খুঁজে বের করতে হবে।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [2, 6, 4, 5, 8], k = 3, তবে আউটপুট হবে 8, কারণ আমরা তালিকাটিকে তিনটি গ্রুপে ভাগ করতে পারি: [2, 6], [4, 5], [8]। তাই ক্ষুদ্রতম গ্রুপের সমষ্টি 8।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

একটি is_divisible() ফাংশন সংজ্ঞায়িত করুন। এটি target নিবে
যদি target <= 1, তবে
- True রিটার্ন করুন
num_chunks := 0, current_sum := 0
nums-এ প্রতিটি x-এর জন্য, করুন
- current_sum := current_sum + x
- যদি current_sum >= target, তবে
  - current_sum := 0
  - num_chunks := num_chunks + 1
  - যদি num_chunks k-এর সমান হয়, তবে
    - True রিটার্ন করুন
False রিটার্ন করুন
মূল মেথড থেকে নিচের কাজগুলো করুন
left := 1
right := (nums-এ সব উপাদানের সমষ্টি) / k + 1
যখন left < right - 1, করুন
- mid := (left + right) / 2
- যদি is_divisible(mid) true হয়, তবে
  - left := mid
- অন্যথায়,
  - right := mid
left রিটার্ন করুন

উদাহরণ (পাইথন)

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

class Solution:    def solve(self, nums, k):       def is_divisible(target):          if target <= 1:             return True          num_chunks = 0          current_sum = 0          for x in nums:             current_sum += x             if current_sum >= target:                current_sum = 0                num_chunks += 1                if num_chunks == k:                   return True          return False       left = 1       right = sum(nums) // k + 1       while left < right - 1:          mid = (left + right) // 2          if is_divisible(mid):             left = mid          else:             right = mid       return left ob = Solution() nums = [2, 6, 4, 5, 8] k = 3 print(ob.solve(nums, k))

ইনপুট

[2, 6, 4, 5, 8], 3