GCD of Odd and Even Sums: Why the Answer Is Always n

Introduction

Every so often you run into a LeetCode problem that looks like it wants you to write a loop and grind through arithmetic — and then you realize the entire problem collapses into a single return statement. GCD of Odd and Even Sums is exactly that kind of problem, and it's a great one to study even though it's labeled "easy," because it tests something interviewers genuinely care about: can you spot structure in a problem before you start coding?

This problem combines two ideas that show up constantly in technical interviews — closed-form summation formulas and the greatest common divisor — and asks you to notice that they interact in a very specific way. If you brute-force it, you'll get the right answer. If you take thirty seconds to think about the structure first, you'll realize you never needed to compute anything at all. That gap between "working solution" and "understood solution" is exactly what separates a junior engineer from a senior one in an interview room, and it's worth internalizing here.

Problem Overview

You're given a positive integer n. Consider the first n odd positive integers (1, 3, 5, …) and the first n even positive integers (2, 4, 6, …). Sum each group separately, call them sumOdd and sumEven. Your task is to return the greatest common divisor of these two sums.

That's the whole problem. No tricky edge cases, no unusual constraints — n is bounded (commonly up to 1000), so even a naive approach runs instantly. The interesting part isn't making it fast; it's noticing that the answer has a closed form.

Example

Let's take n = 4.

• First 4 odd numbers: 1, 3, 5, 7 → sumOdd = 16
• First 4 even numbers: 2, 4, 6, 8 → sumEven = 20
• gcd(16, 20) = 4

Notice the output, 4, is identical to the input, n = 4. That's not a coincidence — it happens for every value of n, and understanding why is the entire point of this problem.

One more example to build confidence, n = 1:

• sumOdd = 1
• sumEven = 2
• gcd(1, 2) = 1

Again, the output equals n.

Intuition

The instinct most people have is to simulate the problem literally: loop through the first n odd numbers, add them up, do the same for even numbers, then run Euclid's algorithm on the two totals. That works, but an experienced engineer's first move on any "compute X then do Y" problem is to ask: is there a closed-form expression for X?

There is. Two classic formulas from arithmetic series:

• Sum of the first n odd numbers = n²
• Sum of the first n even numbers = n(n + 1)

Once you have those, look at the relationship between them:

sumEven = n(n + 1) = n² + n = sumOdd + n

So sumEven is always exactly sumOdd plus n. That's the key structural fact. Now think about what gcd(sumOdd, sumEven) becomes:

gcd(n², n² + n) = gcd(n², n(n + 1)) = n · gcd(n, n + 1)

The last step pulls n out as a common factor of both arguments (this is a standard GCD property: gcd(ka, kb) = k · gcd(a, b)). What's left inside is gcd(n, n + 1) — the GCD of two consecutive integers.

Consecutive integers can never share a common factor greater than 1. If some number d > 1 divided both n and n + 1, it would have to divide their difference, which is 1 — and nothing greater than 1 divides 1. So gcd(n, n + 1) = 1 always.

That means the whole expression simplifies to:

n · 1 = n

The answer is always just n. No sums, no GCD computation, no loop.

Brute Force Solution

Idea: Simulate the problem exactly as stated. Loop to build the first n odd numbers and add them, loop again for even numbers, then compute the GCD (either with a hand-rolled Euclidean algorithm or math.gcd).

Algorithm:

1. Initialize sum_odd = 0, sum_even = 0.
2. Loop i from 1 to n, adding 2i - 1 to sum_odd and 2i to sum_even.
3. Compute gcd(sum_odd, sum_even).
4. Return the result.

Advantages: Requires no insight — you can write it directly from the problem statement. Good for verifying your understanding before optimizing.

Disadvantages: Does real work proportional to n for no benefit, since the result never depends on the actual sums.

Complexity: Time O(n) for the summation loops (plus a negligible O(log(min(sumOdd, sumEven))) for the GCD step). Space O(1).

Optimal Solution

There are really two tiers of "optimal" here, and it's worth understanding both.

Tier 1 — formula-based, still computes the GCD. Use the closed-form sums (n² and n(n+1)) instead of looping, then call math.gcd once. This avoids the loop entirely and trusts the library for the GCD step.

Tier 2 — fully simplified. Since we proved on paper that the result always equals n, skip the sums and the GCD call altogether. Just return n.

Step	Brute force	Formula + gcd	Fully simplified
Compute sumOdd	Loop, O(n)	n**2, O(1)	not needed
Compute sumEven	Loop, O(n)	n*(n+1), O(1)	not needed
Compute GCD	Euclidean loop	math.gcd call	not needed
Return	result	result	n

Tier 2 is what you'd actually ship, but Tier 1 is worth keeping in your back pocket — it's the version you'd write if an interviewer asked you to solve it "without the algebraic trick," and it still demonstrates you know the summation formulas and the standard library.

Python Code

import math


def gcd_of_odd_even_sums_bruteforce(n: int) -> int:
    """Simulates the problem literally: loops and a real GCD call."""
    sum_odd = sum(2 * i - 1 for i in range(1, n + 1))
    sum_even = sum(2 * i for i in range(1, n + 1))
    return math.gcd(sum_odd, sum_even)


def gcd_of_odd_even_sums_formula(n: int) -> int:
    """Uses closed-form sums, still calls math.gcd for clarity/trust."""
    sum_odd = n ** 2
    sum_even = n * (n + 1)
    return math.gcd(sum_odd, sum_even)


def gcd_of_odd_even_sums(n: int) -> int:
    """Optimal: the GCD always equals n, so just return it."""
    return n

Code Walkthrough

• gcd_of_odd_even_sums_bruteforce builds both sums with generator expressions instead of manual loops — same O(n) cost, less boilerplate. math.gcd then runs Euclid's algorithm internally.
• gcd_of_odd_even_sums_formula replaces the loops with the closed-form identities sumOdd = n² and sumEven = n(n+1). This turns two O(n) passes into two arithmetic expressions, each O(1). math.gcd is still called because at this stage we haven't yet exploited the algebraic simplification.
• gcd_of_odd_even_sums is the endpoint of the intuition section: since gcd(n², n(n+1)) = n · gcd(n, n+1) = n · 1 = n, there's nothing left to compute. The function body is the proof, compressed into one line.

Dry Run

Take n = 5 through the formula version:

1. sum_odd = 5 ** 2 = 25
2. sum_even = 5 * 6 = 30
3. math.gcd(25, 30) → factors of 25: 1, 5, 25; factors of 30: 1, 2, 3, 5, 6, 10, 15, 30 → largest shared factor is 5.
4. Return 5, which equals n. Confirms the pattern again.

Complexity Analysis

• Brute force: Time O(n) — dominated by building both sums. Space O(1) beyond the input.
• Formula + gcd: Time is effectively O(log(min(sumOdd, sumEven))), bounded by the Euclidean algorithm's steps, since the sums themselves are computed in constant time. In practice this is a handful of operations regardless of n. Space O(1).
• Fully simplified: Time O(1), space O(1) — there is no dependency on n's magnitude at all.

These are correct because no step in any version does variable-size work beyond what's described — the brute force loops scale linearly with n by construction, while the formula versions replace that loop with fixed-size arithmetic, and the final version replaces even that with a direct return.

Alternative Solutions

You could also derive the result using math.gcd(n, n + 1) directly without ever touching sumOdd or sumEven, then multiply by n — mirroring the algebra step by step in code rather than jumping straight to the conclusion:

def gcd_via_consecutive(n: int) -> int:
    return n * math.gcd(n, n + 1)

This is mathematically equivalent to returning n (since gcd(n, n+1) is always 1), but it's a nice middle-ground version to show in an interview if you want to demonstrate the algebraic reduction without asserting the final simplification outright.

Edge Cases

• n = 1 (minimum): sumOdd = 1, sumEven = 2, gcd = 1. Matches returning n.
• n at maximum (e.g., 1000): Formula and simplified versions handle this instantly with no overflow risk in Python, since integers are arbitrary precision.
• Large n in other languages: Worth noting that n² and n(n+1) could overflow fixed-width integer types in languages like Java or C++ for very large n — not a concern in Python, but worth mentioning if asked.
• No zero or negative input: Constraints guarantee n ≥ 1, so there's no need to guard against n = 0 or negative values.
• Duplicates: Not applicable here since there's no array input, just a single integer.

Common Mistakes

1. Writing a loop to sum odd/even numbers when a closed-form formula exists — wastes time and adds bug surface for no benefit.
2. Reimplementing Euclid's algorithm by hand instead of using math.gcd, introducing off-by-one or infinite-loop risks.
3. Mixing up the even-sum formula — writing n * n instead of n * (n + 1).
4. Assuming the pattern (answer == n) without proving it, then submitting an unverified one-liner that happens to pass small test cases by luck.
5. Forgetting that gcd(a, 0) and other boundary GCD behavior matters in general GCD problems, even though it doesn't surface here since both sums are always positive.

Interview Questions

• Can you prove why gcd(n, n+1) is always 1 for any positive integer n?
• What is gcd(ka, kb) in terms of gcd(a, b), and why does that identity hold?
• How would you extend this to sums of the first n multiples of 3 versus multiples of 5 — is there still a clean closed form?
• What's the time complexity of math.gcd itself, and how does Euclid's algorithm achieve it?
• How would integer overflow change your approach in a language without arbitrary-precision integers?

Similar Problems

• LeetCode 1979 — Find Greatest Common Divisor of Array: Direct practice applying math.gcd across a collection.
• LeetCode 2469 — Convert the Temperature: Different domain, same lesson — spot the formula, skip the simulation.
• LeetCode 1071 — Greatest Common Divisor of Strings: GCD applied to a non-numeric structure, testing whether you understand the concept abstractly rather than just the arithmetic.
• LeetCode 258 — Add Digits: Another "the answer has a closed form, stop simulating" problem, this time tied to digital roots.

Key Takeaways

The core lesson isn't the GCD function itself — it's the habit of asking "does this have a closed form?" before reaching for a loop. Recognizing that sumEven = sumOdd + n turned a two-sum, one-GCD-call problem into a single return statement. That kind of algebraic simplification is exactly what interviewers are probing for when they hand you an "easy" problem: not whether you can write a loop, but whether you look for the shortcut first.

Watch the Video

For the full whiteboard walkthrough of the algebra, plus a side-by-side run of all three solutions, watch the video here: {LINK}

About the Series

This post is part of the Daily Python LeetCode series, where one problem gets fully unpacked every day — the brute force, the optimal approach, and the reasoning that connects them. The goal isn't just passing test cases, it's building the pattern-recognition instincts that make future problems easier.

Call To Action

If this breakdown helped, subscribe on YouTube for the daily video walkthroughs and subscribe to the Substack newsletter for the written version with extra detail. Drop a comment with which problem you'd like covered next, and share this with anyone prepping for interviews.

---

def gcd_of_sums(n: int) -> int:
    sum_odd = sum(2*i+1 for i in range(n))
    sum_even = sum(2*i+2 for i in range(n))
    a, b = sum_odd, sum_even
    while b:
        a, b = b, a % b
    return a