Python प्रोग्राम - सबसे छोटी सबलिस्ट की लंबाई खोजें जिसे हटाकर योग k से विभाज्य हो जाए

सकारात्मक मानों वाली सूची nums और एक सकारात्मक संख्या k दी गई है। हमें सबसे छोटी सबलिस्ट (खाली भी हो सकती है) की लंबाई खोजनी है जिसे हम nums से हटा सकते हैं, ताकि शेष तत्वों का योग k से विभाज्य हो जाए। लेकिन हम पूरी सूची को नहीं हटा सकते। यदि ऐसी कोई सबलिस्ट नहीं है, तो -1 लौटाएं।

उदाहरण

इनपुट: nums = [5, 8, 6, 3], k = 8

आउटपुट: 1

व्याख्या: [5, 8, 6, 3] के तत्वों का वर्तमान योग 22 है। यदि हम लंबाई 1 की सबलिस्ट [6] हटाते हैं, तो योग 16 हो जाता है, जो 8 से विभाज्य है।

एल्गोरिदम (प्रीफिक्स सम + हैश मैप)

1. rem := (sum(nums) + k) % k
2. यदि rem == 0: 0 लौटाएं
3. n := len(nums), presum := 0
4. mp := {0: -1} (डिक्शनरी)
5. res := n
6. i 0 से n-1 तक:
   • presum += nums[i]
   • m := (presum + k) % k
   • mp[m] = i
   • यदि (m - rem + k) % k mp में मौजूद है:
     • res = min(res, i - mp[(m - rem + k) % k])
7. res लौटाएं यदि res != n अन्यथा -1

Python कार्यान्वयन

def solve(nums, k):
    rem = (sum(nums) + k) % k
    if rem == 0:
        return 0
    n, presum = len(nums), 0
    mp = {0: -1}
    res = n
    for i in range(n):
        presum += nums[i]
        m = (presum + k) % k
        mp[m] = i
        if (m - rem + k) % k in mp:
            res = min(res, i - mp[(m - rem + k) % k])
    return res if res != n else -1

nums = [5, 8, 6, 3]
k = 8
print(solve(nums, k))  # आउटपुट: 1

इनपुट/आउटपुट

Input: [5, 8, 6, 3], 8
Output: 1