मान लीजिए हमारे पास धनात्मक मानों वाली एक सूची है, जिसे अंक कहा जाता है और एक धनात्मक संख्या k भी है। हमें सबसे छोटी सबलिस्ट (खाली हो सकती है) की लंबाई का पता लगाना होगा जिसे हम अंकों से हटा सकते हैं, जैसे कि शेष तत्वों का योग k से विभाज्य है। लेकिन हम पूरी सूची नहीं हटा सकते। अगर हटाने के लिए ऐसी कोई सबलिस्ट नहीं है, तो -1 लौटाएं।
इसलिए, यदि इनपुट nums =[5,8,6,3] k =8 जैसा है, तो आउटपुट 1 होगा, क्योंकि [5,8,6,3] के तत्वों का वर्तमान योग 22 है। यदि हम लंबाई 1 की उपसूची [6] हटा दें, तो योग 16 है, जो 8 से विभाज्य है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- रेम :=(अंक + k में मौजूद सभी तत्वों का योग) mod k
- यदि रेम 0 के समान है, तो
- वापसी 0
- n :=अंकों का आकार
- अनुमान :=0
- mp :=एक शब्दकोश, प्रारंभ में कुंजी 0 के लिए -1 स्टोर करें
- res :=n
- मैं के लिए 0 से n -1 की सीमा में, करो
- अनुमान:=अनुमान + अंक[i]
- m :=(presum + k) mod k
- एमपी[एम] :=मैं
- अगर (m - rem + k) mod k mp में मौजूद है, तो
- res :=न्यूनतम रेस और (i - mp[(m - rem + k) mod k])
- रिटर्न रेस अगर रेस n के समान नहीं है अन्यथा -1
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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)) इनपुट
[5,8,6,3], 8
आउटपुट
1