GCD of Odd and Even Sums

Difficulty: Easy | Acceptance: 85.00% | Paid: No Topics: Math, Number Theory

You are given an integer array nums. Return the greatest common divisor (GCD) of the sum of elements at even indices and the sum of elements at odd indices.

• Examples
• Constraints
• Iterative with Euclidean Algorithm
• Using Built-in GCD Function

Examples

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 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Iterative with Euclidean Algorithm

Intuition Calculate the sum of elements at even and odd indices separately, then find their GCD using the Euclidean algorithm.

Steps

• Initialize two variables for even and odd sums
• Iterate through the array, adding elements to their respective sums based on index parity
• Apply Euclidean algorithm to find GCD of the two sums
• Return the GCD

class Solution:
    def gcdOfSums(self, nums: list[int]) -> int:
        even_sum = 0
        odd_sum = 0
        
        for i, num in enumerate(nums):
            if i % 2 == 0:
                even_sum += num
            else:
                odd_sum += num
        
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return abs(a)
        
        return gcd(even_sum, odd_sum)

Complexity

• Time: O(n) where n is the length of the array
• Space: O(1) only using constant extra space
• Notes: Single pass through the array with efficient GCD computation

Using Built-in GCD Function

Intuition Leverage the built-in GCD functions provided by each language’s standard library after computing the sums.

Steps

• Calculate even and odd indexed sums
• Use language’s built-in GCD function
• Return the result

import math

class Solution:
    def gcdOfSums(self, nums: list[int]) -> int:
        even_sum = sum(nums[i] for i in range(0, len(nums), 2))
        odd_sum = sum(nums[i] for i in range(1, len(nums), 2))
        
        return math.gcd(even_sum, odd_sum)

Complexity

• Time: O(n) where n is the length of the array
• Space: O(1) only using constant extra space
• Notes: Cleaner code using built-in functions where available