Python में योग को P से विभाज्य बनाने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट है nums = [8,2,6,5,3], p = 7, तो आउटपुट 1 होगा क्योंकि यदि हम 3 हटाते हैं, तो कुल योग 21 होगा जो 7 से विभाज्य है।

समाधान के चरण

1. ans := infinity
2. s := sum(nums) % p
3. d := {0: -1} (कुंजी-मान जोड़ी वाला मैप)
4. cum := 0
5. यदि s == 0:
   • 0 वापस करें
6. i को 0 से len(nums)-1 तक:
   • cum += nums[i]
   • r := cum % p
   • यदि (r-s)%p d में मौजूद है:
     • ans := min(ans, i - d[(r-s)%p])
   • d[r] := i
7. ans if ans < len(nums) else -1 वापस करें

उदाहरण

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

def solve(nums, p):
    ans = float("inf")
    s = sum(nums) % p
    d = {0: -1}
    cum = 0
    if s == 0:
        return 0
    for i in range(len(nums)):
        cum += nums[i]
        r = cum % p
        if (r - s) % p in d:
            ans = min(ans, i - d[(r - s) % p])
        d[r] = i
    return ans if ans < len(nums) else -1

nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))

इनपुट

[8,2,6,5,3], 7

आउटपुट

1