Welcome to Subscribe On Youtube

3658. GCD of Odd and Even Sums

Description

You are given an integer n. Your task is to compute the GCD (greatest common divisor) of two values:

  • sumOdd: the sum of the first n odd numbers.

  • sumEven: the sum of the first n 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

Solutions

Solution 1: Mathematics

The sum of the first $n$ odd numbers is $n^2$, while the sum of the first $n$ even numbers is $n(n + 1)$. The greatest common divisor of these two is at least $n$. Since $n$ and $n + 1$ are coprime, the answer is $n$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

  • class Solution {
    public int gcdOfOddEvenSums(int n) {
        return n;
    }
}


  • class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};


  • class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n


  • func gcdOfOddEvenSums(n int) int {
	return n
}


  • function gcdOfOddEvenSums(n: number): number {
    return n;
}

All Problems

All Solutions