I'd like to share a problem I wrote a while ago and the solution.
Since we only care about the parity lets transform the array into two integers freqo and freqe.
freqe is the number of even numbers in the array.
freqo is the number of odd numbers in the array.
If we want to make the sum odd then we should take an odd number of odd numbers and an odd number of even numbers, and the opposite is true.
Since $$$2*m \leq n$$$ then only one of the two frequencies can be more than m.
Let's assume $$$freqe < m$$$ and $$$freqo < m$$$ then by adding the two inequalities we get:
$$$freqe + freqo < 2*m$$$ and since $$$freqo + freqe = n$$$ then $$$n < 2*m$$$ which is a contradiction.
Now we have two cases:
- $$$min(freqo,freqe) < m$$$
In this case, the winner is determined by the parity of the minimum of the two.
If it's even then the guy who wants even can take all of it, and the opposite is true.
- $$$min(freqo,freqe) > m$$$
Then the person who starts second always wins by using the mirroring strategy.
freqe = m + a,for some value a. freqo = m + b,for some value b.
If the second person takes always the opposite of what the first person takes then at his last turn he can pick either and odd or and even number and he can choose depending on what he wants the parity to be.
The case 2*m == n can be handled separatly.
