Skip to main content
Talentd

GCD of Odd and Even Sums - Solution & Explanation

EasyMathNumber Theory5 min readAsked at: Microsoft, Google, Bloomberg
Practice this problem

Problem Statement

You are given an integer n. Your task is to compute the GCD (greatest common divisor) of two values:

  • sumOdd: the sum of the smallest n positive odd numbers.

  • sumEven: the sum of the smallest n positive even numbers.

Return the GCD of sumOdd and sumEven.

 

Example 1:

Input: n = 4

Output: 4

Explanation:

  • Sum of the first 4 odd numbers sumOdd = 1 + 3 + 5 + 7 = 16
  • Sum of the first 4 even numbers sumEven = 2 + 4 + 6 + 8 = 20

Hence, GCD(sumOdd, sumEven) = GCD(16, 20) = 4.

Example 2:

Input: n = 5

Output: 5

Explanation:

  • Sum of the first 5 odd numbers sumOdd = 1 + 3 + 5 + 7 + 9 = 25
  • Sum of the first 5 even numbers sumEven = 2 + 4 + 6 + 8 + 10 = 30

Hence, GCD(sumOdd, sumEven) = GCD(25, 30) = 5.

 

Constraints:

  • 1 <= n <= 10​​​​​​​00

Approach Overview

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.

Solution

The sum of the first n odd numbers is n^2, while the sum of the first n even numbers is n(n + 1). The greatest common divisor of these two is at least n. Since n and n + 1 are coprime, the answer is n.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Single Pass Summation + Euclidean GCDO(n)O(1)Best general solution. Scan the array once, compute odd/even sums, then apply GCD.
Incremental GCD AggregationO(n)O(1)Useful when working with streaming data or extremely large sums where periodic reduction helps keep numbers small.

Video Solution

GCD of Odd and Even Sums | Math Proof | Leetcode 3658 | codestorywithMIK • codestorywithMIK • 3,261 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is GCD of Odd and Even Sums easy or hard?
The problem is classified as Easy. It mainly tests understanding of parity checks, basic iteration, and the Euclidean GCD algorithm. Most solutions are short and run in O(n) time with constant space.
GCD of Odd and Even Sums Python/Java solution
The implementation is simple in Python, Java, C++, Go, or TypeScript. Iterate through the array, update sumOdd and sumEven based on parity, and then call a built-in or custom gcd function to return gcd(sumOdd, sumEven). The logic remains identical across languages.
How to solve GCD of Odd and Even Sums in O(n)?
Iterate through the array once and classify each number by parity. Add odd numbers to sumOdd and even numbers to sumEven. After processing all elements, compute gcd(sumOdd, sumEven) using the Euclidean algorithm. The single traversal guarantees O(n) time and constant space.
What is the best approach for GCD of Odd and Even Sums?
The best approach is a single-pass traversal of the array. Compute two running totals: the sum of odd numbers and the sum of even numbers. After the scan, apply the Euclidean algorithm to calculate gcd(sumOdd, sumEven). This runs in O(n) time with O(1) space.
Is GCD of Odd and Even Sums asked at Google/Amazon/Meta?
Problems involving parity separation and GCD calculations appear in coding interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying concepts from math and number theory are frequently tested.
What data structure is used in GCD of Odd and Even Sums?
No specialized data structure is required. The solution only uses a few integer variables to track the running sums of odd and even numbers, along with the Euclidean algorithm to compute the GCD.
What is the time complexity of GCD of Odd and Even Sums?
The overall complexity is O(n), where n is the number of elements in the array. One pass is used to compute the odd and even sums, and the Euclidean GCD calculation takes O(log(min(sumOdd, sumEven))) time, which is negligible compared to the traversal.

Ready to solve this problem?

Practice GCD of Odd and Even Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer