Gismet's blog

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

By Gismet, history, 2 months ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yes, indeed it is almost the same thing I want. Thank you.

    → Reply
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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]]++;

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Damm!! this is a nice idea for solving these types of problems. thanks for the amazing approach

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is a good idea. Thank you.

    → Reply