3658. GCD of Odd and Even Sums
Difficulty: Easy
Topics: Mid Level, Math, Number Theory, Weekly Contest 464
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.
Example 3:
Input: n = 1
Output: 1
Example 4:
Input: n = 2
Output: 2
Example 5:
Input: n = 3
Output: 3
Example 6:
Input: n = 10
Output: 10
Example 7:
Input: n = 100
Output: 100
Example 8:
Input: n = 1000
Output: 1000
Constraints:
1 <= n <= 1000 Hint: The first n odd numbers sum to n * n First n even numbers sum to n * (n + 1) gcd(n, n + 1) = 1, so the answer is n Solution: We solved the problem by recognizing that the GCD of the sum of the first n odd numbers and the sum of the first n even numbers simplifies directly to n. We identified that sumOdd = n² and sumEven = n(n+1), and since n and n+1 are consecutive integers (always coprime), their GCD is 1. Therefore, the answer is simply n, making the solution O(1) time and space complexity. Approach Identify the formulas for the sum of the first n odd and even numbers Recognize that sumOdd = n² and sumEven = n(n+1) Apply GCD properties: gcd(n², n(n+1)) = n × gcd(n, n+1) Use the fact that consecutive integers are always coprime: gcd(n, n+1) = 1 Simplify to get the answer: n × 1 = n Return n directly without computing large sums Let's implement this solution in PHP: 3658. GCD of Odd and Even Sums
Explanation:
Sum of first n odd numbers: The sequence is 1, 3, 5, …, (2n-1). The sum formula is n²
Sum of first n even numbers: The sequence is 2, 4, 6, …, 2n. The sum formula is n(n+1)
GCD calculation: We need gcd(n², n(n+1))
Factor out n: n × gcd(n, n+1) since both terms share a factor of n
Consecutive property: n and n+1 have no common factors other than 1
Final result: n × 1 = n, which matches all test cases
Optimization: No loops or array storage needed; the answer is always the input n
Complexity Analysis
Time Complexity: O(1) – constant time operation, regardless of input size
Space Complexity: O(1) – no additional memory allocation required
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
LinkedIn
GitHub
Sumber Rujukan:
- Artikel asal dari Dev.to PHP
- Published on haqis.com
