LeetCode 3658 - GCD of Odd and Even Sums

LeetCode Problem 3658

Difficulty: 🟢 Easy
Topics: Math, Number Theory

Solution

Problem Understanding

The problem asks us to calculate the greatest common divisor (GCD) of two specific sums derived from an integer input n. The first sum, sumOdd, is the sum of the first n positive odd numbers, and the second sum, sumEven, is the sum of the first n positive even numbers. The input n is guaranteed to be a positive integer between 1 and 1000, so the sums we are dealing with are moderate in size and will comfortably fit within standard integer types in both Python and Go.

The expected output is a single integer representing the GCD of these two sums. For example, if n = 4, the first four odd numbers are 1, 3, 5, and 7, summing to 16. The first four even numbers are 2, 4, 6, and 8, summing to 20. The GCD of 16 and 20 is 4, which should be returned.

Important edge cases include the smallest input n = 1, where the sums are trivially the first odd and first even number, and larger values near n = 1000, which test the arithmetic handling. The problem guarantees positive integers, so we do not need to handle zero or negative inputs.

Approaches

A brute-force approach would compute the sums by explicitly iterating through the first n odd and even numbers and then use a standard GCD function to find the greatest common divisor. While this works for small values, it is unnecessary to iterate because there are closed-form formulas for the sums of the first n odd and even numbers:

• The sum of the first n odd numbers is $n^2$
• The sum of the first n even numbers is $n(n + 1)$

Using these formulas, we can compute the sums directly in constant time, and then compute the GCD of the two results. This observation transforms the problem from a linear-time computation to a constant-time computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Compute sums by iteration, then GCD
Optimal	O(log n)	O(1)	Use formula for sums and Euclidean algorithm for GCD

Algorithm Walkthrough

1. Compute sumOdd using the formula $n^2$. This works because the sum of the first n odd numbers follows a simple arithmetic progression: 1, 3, 5,..., (2n - 1). The sum formula reduces to $n^2$ via arithmetic series sum derivation.
2. Compute sumEven using the formula $n(n + 1)$. The first n even numbers form the sequence 2, 4, 6,..., 2n, which simplifies to 2 * sum(1 to n) = n(n + 1).
3. Compute the GCD of sumOdd and sumEven using the Euclidean algorithm. The algorithm repeatedly replaces the larger number with its remainder when divided by the smaller number until one number becomes zero; the other number is then the GCD.
4. Return the computed GCD as the final result.

Why it works: The algorithm relies on the properties of arithmetic sequences for odd and even numbers, which guarantee the formulas produce the correct sums. The Euclidean algorithm is mathematically proven to compute the GCD efficiently for any pair of integers, ensuring correctness.

Python Solution

import math

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        # Step 1: Compute sum of first n odd numbers
        sumOdd = n * n
        
        # Step 2: Compute sum of first n even numbers
        sumEven = n * (n + 1)
        
        # Step 3: Compute and return the GCD
        return math.gcd(sumOdd, sumEven)

This implementation computes sumOdd and sumEven using the derived formulas in constant time. The math.gcd function handles the GCD calculation efficiently, and the function returns the result. The solution avoids unnecessary loops, ensuring optimal performance.

Go Solution

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func gcdOfOddEvenSums(n int) int {
    // Compute sum of first n odd numbers
    sumOdd := n * n
    
    // Compute sum of first n even numbers
    sumEven := n * (n + 1)
    
    // Compute and return the GCD
    return gcd(sumOdd, sumEven)
}

In Go, we implement a helper function gcd to compute the greatest common divisor using the iterative Euclidean algorithm. The sum calculations follow the same formulas as in Python. No slices or arrays are required since the sums are computed directly.

Worked Examples

Example 1: n = 4

Step	sumOdd	sumEven	GCD
Compute sums	4^2 = 16	4 * 5 = 20
Compute GCD	16	20	4

Example 2: n = 5

Step	sumOdd	sumEven	GCD
Compute sums	5^2 = 25	5 * 6 = 30
Compute GCD	25	30	5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	The sums are computed in O(1), but the GCD of two numbers ≤ n(n+1) is O(log(n(n+1))) = O(log n)
Space	O(1)	Only a few integer variables are used; no additional data structures

The Euclidean algorithm dominates the complexity, but the sums are calculated in constant time.

Test Cases

# Provided examples
assert Solution().gcdOfOddEvenSums(4) == 4  # sumOdd=16, sumEven=20
assert Solution().gcdOfOddEvenSums(5) == 5  # sumOdd=25, sumEven=30

# Edge cases
assert Solution().gcdOfOddEvenSums(1) == 1  # smallest n
assert Solution().gcdOfOddEvenSums(2) == 2  # sumOdd=1+3=4, sumEven=2+4=6, GCD=2
assert Solution().gcdOfOddEvenSums(1000) == 1000  # large n

# Additional cases
assert Solution().gcdOfOddEvenSums(10) == 10  # sumOdd=100, sumEven=110
assert Solution().gcdOfOddEvenSums(7) == 7  # sumOdd=49, sumEven=56

Test	Why
n=4, n=5	Provided examples for correctness
n=1	Minimal input edge case
n=2	Small input, tests formula correctness
n=1000	Large input, tests arithmetic correctness and integer handling
n=7, n=10	Additional arbitrary examples to validate GCD calculation

Edge Cases

One important edge case is n = 1, where the sums are 1 (odd) and 2 (even). This tests the lower bound and ensures the formulas n^2 and n(n+1) do not fail for small numbers.

Another edge case occurs with large n near 1000. The sums reach n^2 = 1000000 and n(n+1) = 1001000. This tests that the language can handle large integer arithmetic without overflow. Python inherently supports arbitrary precision integers, while Go relies on standard integer types; in this range, int is sufficient.

Finally, cases where n is prime, such as n = 7 or n = 13, are interesting because the GCD is exactly n, which validates the mathematical property that GCD(n^2, n(n+1)) = n when n and n+1 are coprime. This ensures the algorithm works correctly for both composite and prime inputs.