Skip to content

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

Solutions

Solution 1: Mathematics

Thinking

The first \(n\) odds sum to \(n^2\) and the first \(n\) evens sum to \(n(n+1)\). Any common divisor is a multiple of \(n\).

Since \(n\) and \(n+1\) are coprime, \(\gcd(n^2,n(n+1))=n\). A generic gcd loop is unnecessary.

Return \(n\).

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)\).

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

1
2
3
4
5
class Solution {
    public int gcdOfOddEvenSums(int n) {
        return n;
    }
}

1
2
3
4
5
6
class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};

1
2
3
func gcdOfOddEvenSums(n int) int {
    return n
}

1
2
3
function gcdOfOddEvenSums(n: number): number {
    return n;
}

1
2
3
4
5
impl Solution {
    pub fn gcd_of_odd_even_sums(n: i32) -> i32 {
        n
    }
}

1
2
3
4
5
public class Solution {
    public int GcdOfOddEvenSums(int n) {
        return n;
    }
}

Comments