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

मान लीजिए हमारे पास 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
- प्रत्येक x in nums के लिए:
  - current_sum += x
  - यदि current_sum >= target:
    - current_sum=0, num_chunks++
    - यदि num_chunks == k, तो True वापस करें
- False वापस करें
मुख्य विधि से:
- left=1, right=sum(nums)//k + 1
- जब left < right-1:
  - mid = (left+right)//2
  - यदि is_divisible(mid), तो 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