पायथन का उपयोग करके विषम योग के साथ उप-सरणियों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी है। हमें विषम योग के साथ उप-सरणियों की संख्या ज्ञात करनी है। अगर उत्तर बहुत बड़ा है तो परिणाम मॉड्यूल 10^9+7 लौटाएं।

इसलिए, यदि इनपुट arr =[8,3,7] जैसा है, तो आउटपुट 3 होगा क्योंकि सभी उप सरणियाँ [[8], [3], [7], [8,3], [3] हैं। 7],[8,3,7]] अब उनका योग मान [8,3,7,11,10,18] है, इसलिए तीन विषम योग मान हैं [3,7,11]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• freq :=दो तत्वों 1 और 0 के साथ एक सूची

• उत्तर :=0

• उपसर्ग :=0

• गिरफ्तारी में प्रत्येक x के लिए, करें

  • उपसर्ग :=उपसर्ग + x

  • उत्तर:=उत्तर + फ़्रीक[1 XOR उपसर्ग और 1]

  • freq[उपसर्ग और 1]:=freq[उपसर्ग और 1] + 1

• वापसी उत्तर मोड (10^9+7)

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

उदाहरण

def solve(arr):
   freq = [1, 0]
   ans = prefix = 0
   for x in arr:
      prefix += x
      ans += freq[1 ^ prefix&1]
      freq[prefix &s; 1] += 1
   return ans % (10**9+7)
arr = [8,3,7]
print(solve(arr))

इनपुट

[8,3,7]

आउटपुट

3