পাইথন ব্যবহার করে বিজোড় যোগফল সহ সাব-অ্যারের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে অ্যারে আছে। আমাদের বিজোড় যোগফল সহ সাব-অ্যারের সংখ্যা বের করতে হবে। যদি উত্তরটি খুব বড় হয় তাহলে ফলাফল মডিউল 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 এর জন্য arr, করুন

  • উপসর্গ :=উপসর্গ + x

  • ans :=ans + freq[1 XOR উপসর্গ এবং 1]

  • freq[উপসর্গ AND 1] :=freq[উপসর্গ AND 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