मान लीजिए कि हमारे पास एक सरणी संख्या और एक अन्य मान p है, तो हम सबसे छोटी उपसरणी (संपूर्ण सरणी नहीं) को हटाते हैं जैसे कि शेष मानों का योग p से विभाज्य हो। हमें सबसे छोटे सबअरे की लंबाई का पता लगाना है जिसे हमें हटाने की जरूरत है, अगर ऐसा कोई सबरे नहीं है तो रिटर्न -1।
इसलिए, यदि इनपुट nums =[8,2,6,5,3] p =7 जैसा है, तो आउटपुट 1 होगा क्योंकि यदि हम 3 को हटा दें, तो कुल योग 21 होगा और वह 7 से विभाज्य है। /पी>
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- उत्तर:=अनंत
- s :=(संख्याओं में सभी तत्वों का योग) mod p
- d :=एक मैप में की-वैल्यू पेयर होता है {0:-1}
- सह:=0
- यदि s 0 के समान है, तो
- वापसी 0
- मैं के लिए 0 से लेकर अंकों के आकार तक, करें
- सह:=सह + अंक[i]
- r :=कम मॉड p
- अगर (r-s)mod p, d में मौजूद है, तो
- उत्तर :=न्यूनतम उत्तर और i - d[(r-s) mod p]
- d[r] :=i
- वापसी उत्तर यदि उत्तर <अंकों का आकार अन्यथा -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