Maximum Even-Sum Neighboring Pairs

You are given N numbers on a circle, described by an integer array A. A neighboring pair is formed by two adjacent positions on the circle. This means positions i and i + 1 are neighbors, and the last position is also a neighbor of the first position.
Your task is to find the maximum number of neighboring pairs whose sums are even. Each array element can belong to at most one chosen pair.

Function
solution(A: int[]) → int

Examples
Example 1
A = [4,2,5,8,7,3,7]
return = 2
One optimal choice is (A[0], A[1]) and (A[4], A[5]). Another optimal choice is (A[0], A[1]) and (A[5], A[6]).
Choice 1: 4, 2, 5, 8, 7, 3, 7
Choice 2: 4, 2, 5, 8, 7, 3, 7
Example 2
A = [14,21,16,35,22]
return = 1
The only qualifying neighboring pair is (A[0], A[4]), using the circular adjacency between the first and last elements.
Circular pair: 14, 21, 16, 35, 22
Example 3
A = [5,5,5,5,5,5]
return = 3
All neighboring sums are even. We can create three non-overlapping pairs, for example (A[0], A[5]), (A[1], A[2]), and (A[3], A[4]).

Reduce the array to parity. Adjacent elements form an even-sum pair only if they're both odd or both even. So split the circle into maximal runs of equal parity. A run of length L gives floor(L/2) disjoint adjacent pairs. Sum those across runs. The trap is the wraparound. If the first and last elements share parity, the first run and last run merge into one circular run, so you can't count them separately. If every element has the same parity, the whole circle is one run of N, and the answer is floor(N/2), which matches Example 3 giving 3 for six fives. Handle it by rotating the start to a parity boundary, or by merging the first and last run lengths. One linear pass, O(N) time, O(1) space. If the circular merge slips your mind mid-assessment, StealthCoder is the hedge that catches it live.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.