মান লাগিয়ে, আমাদের একটি অ্যারে arr আছে। আমাদের অড্ড সম ওয়ালা সাব-অ্যারে সংখ্যা বের করতে হবে। যদি উত্তর খুব বড় হয়, তবে 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] দিয়ে একটি লিস্ট
- ans := 0
- prefix := 0
- arr-এ থাকা প্রতিটি x জন্য:
- prefix := prefix + x
- ans := ans + freq[1 XOR prefix AND 1]
- freq[prefix AND 1] := freq[prefix AND 1] + 1
- ans mod (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]
print(solve(arr))
ইনপুট
[8,3,7]
আউটপুট
3
