Greatest Common Divisor of Odd and Even Sums
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Given a positive integer `n`, form two sums:
- `sumOdd`: the sum of the smallest `n` positive odd integers;
- `sumEven`: the sum of the smallest `n` positive even integers.
Return their greatest common divisor: the largest positive integer dividing both sums.
```cpp
class Solution {
public:
int gcdOfOddEvenSums(int n);
};
```
### Examples
**Example 1:**
```text
Input: n = 1
Output: 1
Explanation: The two sums are 1 and 2, whose greatest common divisor is 1.
```
**Example 2:**
```text
Input: n = 6
Output: 6
Explanation: The odd sum is 1+3+5+7+9+11 = 36. The even sum is 2+4+6+8+10+12 = 42. Their greatest common divisor is 6.
```
### Constraints
- `1 <= n <= 1000`.
### Clarifying Questions
- Does the even sequence include zero? No. It starts at 2 because the terms are positive.
- Are there `n` terms in each sum? Yes, independently.
- Is the requested result the greatest common divisor or the least common multiple? The greatest common divisor.
### What a Strong Answer Covers
- The exact two positive-integer sequences and the number of terms in each.
- A justification of the returned greatest common divisor.
- The smallest and largest allowed inputs.
- Appropriate numeric bounds and resource complexity.
### Follow-up Questions
- What would the two sums be if the even sequence were instead defined to start at zero?
- How should the result be interpreted when the two sums have many common divisors?
```hint Use the arithmetic-series sums
Write each sum in terms of n, then apply a greatest-common-divisor identity rather than constructing the sequences.
```
Overview: Find the greatest common divisor of the first n positive odd-number and even-number sums, with examples, a proof, bounds, and a concise C++ solution.