Блог пользователя Gismet

Find the number of subarrays where the even numbers appear odd number of times.

Автор Gismet, история, 6 недель назад, По-английски

I was solving subarray problems the other day and came up with the above problem. I searched it online. I just wanted to solve it and submitted it to a judge. But I could not find such a problem. Do you guys happen to have encounter such a problem somewhere?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
6 недель назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

This problem is the same concept you want. You need to find subarray where even appears odd no time but in this problem you have to find odd number appears odd number of time because odd number appeared odd times so the sum is odd

→ Ответить
»
6 недель назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

You can re-structure the problem like ->

assign 0 to every odd number and 1 to every even number, now you just need to find the subarray which have XOR = 1, For this you can maintain prefix_XOR AND count of prefix XOR'S since the XOR Value will either be 1 or 0 only.

Taking index i as the right end point of the subarray you will do ->

ans += prefix_count[prefix_xor[i]^1];

and u will update prefix_count[prefix_xor[i]]++;

→ Ответить