Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

GCD of Odd and Even Sums solution and explanation

EasyMathNumber Theory3 min read89.8% acceptanceUpdated 24 Mar 2026
Asked atGoogleMicrosoftBloomberg
Practise GCD of Odd and Even Sums
10:25
GCD of Odd and Even Sums | Math Proof | Leetcode 3658 | codestorywithMIKcodestorywithMIK · 10:25 · 3K viewsWatch on YouTube
9 more videos on this problem
  1. GCD of Odd and Even Sums | Math Proof | Leetcode 3658 | codestorywithMIKcodestorywithMIK · 10:25 · 3K views
  2. 3658. GCD of Odd and Even Sums (Leetcode Easy)Programming Live with Larry · 4:54 · 463 views
  3. 3658. GCD of Odd and Even Sums | Leetcode Daily - PythonLeetcode Daily · 5:38 · 288 views
  4. GCD of Odd and Even Sums | LeetCode 3658 - Pythonimpoldev · 5:30 · 234 views
  5. Daily Leetcode #2297: Jul 15, 2026 - 3658. GCD of Odd and Even SumsProgramming Live with Larry · 6:40 · 195 views
  6. 3658. GCD of Odd and Even Sums | Leetcode Weekly Contest 464Break and Build · 9:04 · 156 views
  7. Leetcode 3658 GCD of Odd and Even Sums - Explained Well!AlgorithmicIQ · 10:46 · 141 views
  8. GCD of Odd and Even Sums | Simple Thought Process | Leetcode 3658CodeWith_Kedar · 8:15 · 97 views
  9. GCD of Odd and Even Sums | Leetcode - 3658Shivam Gupta · 6:14 · 87 views
  10. LeetCode 3658 | GCD of Odd and Even Sums | Java Solution | Math | CodeByTushuCodeByTushu · 2:24 · 62 views

The problem

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

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n
class Solution {
    public int gcdOfOddEvenSums(int n) {
        return n;
    }
}
class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};
function gcdOfOddEvenSums(n: number): number {
    return n;
}
func gcdOfOddEvenSums(n int) int {
	return n
}
Try this approach in the editor

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.

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.

Comments

Now write it yourselfClose this page and solve GCD of Odd and Even Sums in the editor, without looking.
Practise GCD of Odd and Even Sums