3658. GCD of Odd and Even Sums

EasyView on LeetCode

Math Number Theory

Time: O(1)

Space: O(1)

Problem Overview

You need gcd(sum of first n odds, sum of first n evens).

Intuition

You need gcd(sum of first n odds, sum of first n evens). Closed forms are sumOdd = n² and sumEven = n(n+1). Factor out n: gcd(n², n(n+1)) = n · gcd(n, n+1). Consecutive integers are always coprime, so gcd(n, n+1) = 1 and the answer is simply n.

Algorithm

1Recall: 1+3+…+(2n−1) = n².
2Recall: 2+4+…+2n = n(n+1).
3Return n — no need to compute the sums or run Euclidean GCD.

Example Walkthrough

Input: n = 4

1.sumOdd = 1+3+5+7 = 16 = 4².
2.sumEven = 2+4+6+8 = 20 = 4·5.
3.gcd(16, 20) = 4, which equals n.

Output: 4

Common Pitfalls

•Do not loop to build the odd/even lists — the O(1) identity is the intended solution.
•gcd(n, n+1) is always 1; do not special-case n = 1 (still returns 1 correctly).
•Constraints are small enough for a loop, but returning n is both correct and optimal.

3658.cs

// Approach: Math identity — sum of first n odds = n², sum of first n evens = n(n+1).
// gcd(n², n(n+1)) = n * gcd(n, n+1) = n since consecutive integers are coprime.
// Time: O(1) Space: O(1)
public class Solution
{
    public int GcdOfOddEvenSums(int n)
    {
        return n;
    }
}

Was this solution helpful?