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

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

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন is_divisible() সংজ্ঞায়িত করুন। এটি লক্ষ্য গ্রহণ করবে

• যদি লক্ষ্য <=1, তারপর

  • রিটার্ন ট্রু

• num_chunks :=0, current_sum :=0

• প্রতিটি x সংখ্যায়, করুন

  • বর্তমান_সমষ্টি :=বর্তমান_সমষ্টি + x

  • যদি বর্তমান_সম>=টার্গেট, তাহলে

    • বর্তমান_সমষ্টি :=0

    • num_chunks :=num_chunks + 1

    • যদি num_chunks k এর মত হয়, তাহলে

      • রিটার্ন ট্রু

• রিটার্ন ফলস

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• বাকি :=1

• ডান :=(সংখ্যায় সমস্ত উপাদানের যোগফল) / k + 1

• যখন বামে <ডান - 1, করুন

  • মধ্য :=(বাম + ডান) / 2

  • যদি is_divisible(mid) সত্য হয়, তাহলে

    • বাম :=মধ্য

  • অন্যথায়,

    • ডান :=মধ্য

• বাম দিকে ফিরে যান

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

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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

আউটপুট

8