GCD of Odd and Even Sums - Video Solutions

Problem Overview: You are given a list of integers and need to compute two values: the sum of all odd numbers and the sum of all even numbers. The final answer is the gcd(sumOdd, sumEven). The challenge is straightforward but relies on understanding parity and using the Euclidean algorithm efficiently.

Approach 1: Single Pass Summation + Euclidean GCD (O(n) time, O(1) space)

Traverse the array once and maintain two running totals: sumOdd and sumEven. For each element, check parity using num % 2. Add odd values to sumOdd and even values to sumEven. After the scan completes, compute gcd(sumOdd, sumEven) using the Euclidean algorithm, which repeatedly applies gcd(a, b) = gcd(b, a % b) until the remainder becomes zero.

This approach works because the problem reduces to a pure number theory operation once the two sums are known. The array is processed exactly once, so the traversal cost is linear. The GCD computation itself runs in O(log(min(sumOdd, sumEven))), which is effectively constant relative to the array size.

Space usage stays O(1) since only two integers are tracked. This is the cleanest and most practical solution for interviews and production code.

Approach 2: Incremental GCD Aggregation (O(n) time, O(1) space)

Another way to think about the problem is to accumulate the odd and even sums while periodically reducing them using the GCD property. During iteration, maintain the same two totals, but you can simplify intermediate values by applying the Euclidean reduction when numbers grow large. Because gcd(a + b, c) = gcd(gcd(a, c) + b, c), the final result remains unchanged.

This technique is occasionally useful when sums can become extremely large or when working with streaming data. In typical interview constraints it behaves the same as the basic summation method and still runs in O(n) time with O(1) space.

The core ideas come from math and number theory, specifically parity classification and the Euclidean GCD algorithm.

Recommended for interviews: Use the single-pass summation plus Euclidean GCD approach. Interviewers expect you to immediately separate odd and even values during one traversal and compute the GCD at the end. A brute-force idea (recomputing sums multiple times) shows basic reasoning, but the optimal O(n) pass demonstrates comfort with parity checks and fundamental math operations.