Is GCD of Odd and Even Sums easy or hard?

The problem is classified as Easy. It mainly tests understanding of parity checks, basic iteration, and the Euclidean GCD algorithm. Most solutions are short and run in O(n) time with constant space.

GCD of Odd and Even Sums Python/Java solution

The implementation is simple in Python, Java, C++, Go, or TypeScript. Iterate through the array, update sumOdd and sumEven based on parity, and then call a built-in or custom gcd function to return gcd(sumOdd, sumEven). The logic remains identical across languages.

How to solve GCD of Odd and Even Sums in O(n)?

Iterate through the array once and classify each number by parity. Add odd numbers to sumOdd and even numbers to sumEven. After processing all elements, compute gcd(sumOdd, sumEven) using the Euclidean algorithm. The single traversal guarantees O(n) time and constant space.

What is the best approach for GCD of Odd and Even Sums?

The best approach is a single-pass traversal of the array. Compute two running totals: the sum of odd numbers and the sum of even numbers. After the scan, apply the Euclidean algorithm to calculate gcd(sumOdd, sumEven). This runs in O(n) time with O(1) space.

Is GCD of Odd and Even Sums asked at Google/Amazon/Meta?

Problems involving parity separation and GCD calculations appear in coding interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying concepts from math and number theory are frequently tested.

What data structure is used in GCD of Odd and Even Sums?

No specialized data structure is required. The solution only uses a few integer variables to track the running sums of odd and even numbers, along with the Euclidean algorithm to compute the GCD.

What is the time complexity of GCD of Odd and Even Sums?

The overall complexity is O(n), where n is the number of elements in the array. One pass is used to compute the odd and even sums, and the Euclidean GCD calculation takes O(log(min(sumOdd, sumEven))) time, which is negligible compared to the traversal.

Description Hints 3 Solution Video 10:25

3658. GCD of Odd and Even Sums

Easy89.8% acceptance3 companies

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 <= 1000

Asked at 3 companies

Google Microsoft Bloomberg

Topics

Math Number Theory

Hints open one at a time

Hint 1

The first n odd numbers sum to n * n

Hint 2

First n even numbers sum to n * (n + 1)

Hint 3

gcd(n, n + 1) = 1, so the answer is n

10:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def gcdOfOddEvenSums(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution