How do you find the longest subarray of alternating even and odd numbers?
Short answer: Walk the array once with a running count. If the current element has a different parity from the previous one, extend the run (count++); otherwise restart it at 1. Track the maximum. O(n) time, O(1) space.
#include <stddef.h>
size_t longest_even_odd(const int *arr, size_t n)
{
if (n == 0) return 0;
size_t best = 1, count = 1;
for (size_t i = 1; i < n; i++) {
if ((arr[i] % 2 == 0) != (arr[i - 1] % 2 == 0)) { /* parity changed */
count++;
if (count > best) best = count;
} else {
count = 1;
}
}
return best;
}
/* {5, 10, 20, 6, 3, 8} -> 3 (6, 3, 8) */
/* {10, 12, 8, 4} -> 1 */
Simplifying the condition. The long form ((a%2==0) && (b%2!=0)) || ((a%2!=0) && (b%2==0)) is "exactly one of them is even", which is a single inequality of two booleans: (a % 2 == 0) != (b % 2 == 0). A bitwise version is ((a ^ b) & 1) != 0: the lowest bits differ exactly when the parities differ, and it works for negative numbers in two's complement.
Negative numbers: -3 % 2 is -1 in C, so a test like a % 2 == 1 treats -3 as even. Comparing with == 0 (or using & 1) avoids this.
Dry run for {5, 10, 20, 6, 3, 8}: 5→10 change (2), 10→20 same (reset 1), 20→6 same (1), 6→3 change (2), 3→8 change (3). Answer 3.
Pattern: this is the "longest run satisfying a condition between neighbours" template. The same loop solves "longest increasing contiguous run", "max consecutive ones" and "longest run of equal values".