पायथन में कम से कम आकार 2 का सबलिस्ट खोजने का प्रोग्राम जिसका योग k का गुणक है

मान लीजिए हमारे पास गैर-ऋणात्मक संख्याओं की एक सूची nums और एक धनात्मक मान k है। हमें जांचना है कि क्या कम से कम लंबाई 2 का कोई सबलिस्ट है जिसका योग k का गुणक है या नहीं।

उदाहरण के लिए, यदि इनपुट nums = [12, 6, 3, 4] और k = 5 है, तो आउटपुट True होगा, क्योंकि सबलिस्ट [12, 3] का योग 15 है जो 5 से विभाज्य है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (प्रीफिक्स सम मॉड्यूलो + हैशमैप):

• sum := 0
• m := एक नया मैप, m[0] := -1
• i को 0 से len(nums) तक:
  • sum += nums[i], sum %= k
  • यदि sum in m:
    • यदि i - m[sum] >= 2: True लौटाएं
  • अन्यथा: m[sum] = i
• False लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums, k):
        sum = 0
        m = {}
        m[0] = -1
        for i in range(len(nums)):
            sum += nums[i]
            sum %= k
            if sum in m:
                if i - m[sum] >= 2:
                    return True
            else:
                m[sum] = i
        return False

ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))

इनपुट

[12, 6, 3, 4], 5

आउटपुट

True