Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Gismet's blog

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

By Gismet, history, 6 weeks 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

»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is a good idea. Thank you.

    → Reply