पायथन में सबसे बड़े K-विभाज्य सबसीक्वेंस योग ज्ञात करने का प्रोग्राम

मान लीजिए हमें गैर-ऋणात्मक संख्याओं की एक सूची और एक धनात्मक मान k दिया गया है। हमें संख्याओं का अधिकतम योग वाला सबसीक्वेंस ढूंढना है जो k से विभाज्य हो।

उदाहरण के लिए, nums = [4,6,8,2], k=2 के लिए आउटपुट 20 होगा (पूरी सरणी का योग 20, जो 2 से विभाज्य है)।

एल्गोरिदम

• numsSum := nums का योग, remainder := numsSum % k
• यदि remainder == 0, तो numsSum वापस करें
• nums को सॉर्ट करें
• सभी संभावित सबसेट tpl के लिए:
  • subSeqSum := sum(tpl)
  • यदि subSeqSum % k == remainder, तो numsSum - subSeqSum वापस करें
• 0 वापस करें

उदाहरण

from itertools import chain, combinations
class Solution:
    def solve(self, nums, k):
        numsSum = sum(nums)
        remainder = numsSum % k
        if remainder == 0: return numsSum
        nums.sort()
        for tpl in chain.from_iterable(combinations(nums, r) for r in range(1, len(nums)+1)):
            subSeqSum = sum(tpl)
            if subSeqSum % k == remainder:
                return numsSum - subSeqSum
        return 0

ob1 = Solution()
print(ob1.solve([4,6,8,2], 2))

इनपुट

[4, 6, 8, 2], 2

आउटपुट

20