प्रीफिक्स सम पैरिटी (इवन/ऑड) फ्रीक्वेंसी से ऑड सम वाले सबअर्रे काउंट करें। मॉड्यूलो 10⁹+7।
एल्गोरिदम
freq = [1, 0](प्रीफिक्स सम इवन=1, ऑड=0 से शुरू)।prefix= करंट प्रीफिक्स सम पैरिटी (0=इवन, 1=ऑड)।- प्रत्येक x के लिए:
prefix ^= (x & 1),ans += freq[1 ^ prefix],freq[prefix]++। ans % (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 & 1] += 1
return ans % (10**9 + 7)
# टेस्ट: arr=[8,3,7] -> सबअर्रे: [8],[3],[7],[8,3],[3,7],[8,3,7]
# सम: 8,3,7,11,10,18 -> ऑड: 3,7,11 -> काउंट=3
इनपुट/आउटपुट
इनपुट: [8,3,7]
आउटपुट: 3
