</>EmbeddedInterview

How do you find the longest subarray of alternating even and odd numbers?

MediumArrays & Strings (Coding Round)

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".