Number of Sub-arrays With Odd Sum

Sizga butun sonlardan iborat arr massivi berilgan. Yig'indisi toq (odd) bo'lgan barcha qism-massivlarning sonini toping.

Natijani 10^9 + 7 ga bo'lingandagi qoldig'ini qaytaring.

Qism-massiv ketma-ket joylashgan elementlardan iborat. Yig'indi prefiks yig'indilari juftligi orqali hisoblanadi: toq yig'indi = (toq prefiks) − (juft prefiks) yoki aksincha.

func solve(arr []int) int {
    // ...
}

Misollar

Input: arr = [1,3,5]
Output: 4
Tushuntirish: [1], [3], [5] va [1,3,5] — barchasi toq yig'indili qism-massivlar.

Input: arr = [2,4,6]
Output: 0

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Maslahatlar

1. Har bir qism-massivni alohida tekshirish shart emas — prefiks yig'indilarning juft/toqligini kuzatib borsangiz, qism-massiv yig'indisining juft yoki toqligini tezda aniqlash mumkinligini o'ylab ko'ring.
2. Joriy prefiks yig'indisining juft yoki toq ekanligini hisoblab boring va shu vaqtgacha uchragan juft hamda toq prefikslar sonini alohida sanang; joriy prefiks juft bo'lsa, undan oldingi toq prefikslar soni javobga qo'shiladi (chunki ular orasidagi farq toq bo'ladi), joriy prefiks toq bo'lsa, undan oldingi juft prefikslar soni qo'shiladi — natijani modul bo'yicha yig'ib boring.