Skip to content

3658. GCD of Odd and Even Sums

SourceWeekly Contest 464 Q1DifficultyEasyRating1220

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