पायथन में सबसे छोटे समूह का अधिकतम संभव मूल्य खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है। हमें सूची को k सन्निहित समूहों में विभाजित करना होगा। सबसे छोटा समूह वह होता है जिसका योग सभी समूहों में सबसे छोटा होता है। अतः सबसे छोटे समूह का अधिकतम संभव मान ज्ञात कीजिए।

इसलिए, यदि इनपुट संख्या =[2, 6, 4, 5, 8] k =3 की तरह है, तो आउटपुट 8 होगा, क्योंकि हम सूची को तीन समूहों में विभाजित कर सकते हैं जैसे:[2, 6], [4 , 5], [8]। तो न्यूनतम समूह का योग 8 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें is_divisible() । यह लक्ष्य लेगा

• अगर लक्ष्य <=1, तो

  • सही लौटें

• num_chunks :=0, current_sum :=0

• अंकों में प्रत्येक x के लिए, करें

  • current_sum :=current_sum + x

  • अगर current_sum>=लक्ष्य, तो

    • current_sum :=0

    • num_chunks :=num_chunks + 1

    • अगर num_chunks k के समान है, तो

      • सही लौटें

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• बायां :=1

• दाएं:=(संख्याओं में सभी तत्वों का योग) / k + 1

• जबकि बाएं <दाएं -1, करें

  • मध्य:=(बाएं + दाएं) / 2

  • यदि is_divisible(मध्य) सत्य है, तो

    • बाएं :=मध्य

  • अन्यथा,

    • दाएं:=मध्य

• बाएं लौटें

उदाहरण (पायथन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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