Given a circular array of N integers (that is, 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.
For example, if we have [5, 7, 9, 6, 3], then you should pair (5, 3) and (7, 9) to achieve the answer of two. Also, if we have [1, 1, 1, 1, 1, 1], then the answer is 3 (pair each adjacent element without wrapping around)
This is a recent problem that I encountered in an interview, and I still can't solve it (I didn't get the job). 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? I was thinking perhaps something with dynamic programming, but I'm not sure. The circular part is really throwing me off.
Thanks.