Given a circular array of N integers (i.e. A[0] and A[N — 1] are adjacent to each other), what's the maximum number of adjacent pairs that you can form whose sum are even? Note that each element can belong to at most one pair.
This is a recent problem that I encountered, but my approach is wrong. I know that the sum of two numbers of the same parity produce an even sum (so odd and odd, or even and even), but the whole "wrap-around" part is what's getting me. In particular, I can't figure out whether or not it's optimal to pair a value with its left neighbor or its right neighbor. The current algorithm I'm thinking of is as follows:
For each index 0 <= i <= n — 1, try to pair A[i] with A[i + 1] by checking their parity.
If both A[0] and A[n — 1] are unpaired at the end, pair them if they have the same parity.
This is a wrong algorithm since it fails for [1, 1, 1, 0, 1] in which case it's optimal to pair A[0] with A[n — 1] and A[1] with A[2]. Does anyone have any suggestions?
Thanks.
For each element only their parity matters. Also elements of different parities cannot be paired together.
Decompose the array into several continuous chains. E.g.
[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1] ==>
[1, 1, 1, 1, 1] (The chain at position 1, 2, 3 as well as the last two, since it's circular)
[0, 0, 0]
[1]
[0, 0]
For each chain the answer is floor(len(chain) / 2).
As you can see the pairing of each chain cannot affect other chain and theres no cross-chain pairing, so we can sum the answers for each chain.
Each number is odd or even, we can pair two of same kind. The circ array is formed by segments of elements of odd or even. In each segment we can create size/2 pairs. So the circ array behaves like a linear array if the circ is cutted at a segment boundary.