Link: https://leetcode.com/problems/gcd-of-odd-and-even-sums/description/

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

Analysis#

The straightforward approach takes two steps:

1. Compute the sum of the first n even numbers and the sum of the first n odd numbers: each sum needs one for loop running up to n to accumulate the total.
2. From those two numbers, find their greatest common divisor -> usually a while loop over the two values, taking the remainder of the division and reassigning it back (this is the Euclidean algorithm).

Analysis: Step 1 has time complexity O(n) and negligible space complexity, since we only keep two numbers. Step 2 is governed by Lamé’s theorem, which states:

The number of steps the Euclidean algorithm takes to find the greatest common divisor (GCD) of any two positive integers never exceeds (5) times the number of (decimal) digits of the smaller number

However, with the constraint n max = 1000, this approach runs into a problem. When n = 1000, sumOdd is 1000000 and sumEven is 1001000. That is 7 digits => the maximum number of steps can be 35 divide-and-reassign iterations inside the while loop. Loosely speaking, 35 operations plus 1000 loop iterations still gives a small time complexity. But in a real interview, not many candidates can state the time complexity precisely, because they cannot recall Lamé’s theorem, and they may lose time re-implementing Euclid from scratch. Easy to get failed even though the solution works.

A new approach: At heart, the problem relies on a classic property of arithmetic series.

1 + 3 + 5 + … + (2n-1) = n ^ 2

2 + 4 + 6 + .. + 2n = n * (n+1)

Step 1 now becomes instant: time complexity O(n) -> O(1). And by Euclid, the modulo finishes immediately in a single operation, because: (n * (n+1)) / n^2 = n => O(1). So we get a solution with time complexity O(1) and space O(1), as below:

/**
 * @param {number} n
 * @return {number}
 */
var gcdOfOddEvenSums = function(n) {
    return n;
};