Split a Sum into as Many Distinct Positive Evens as Possible
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Split `finalSum` into distinct positive even integers, using as many terms as possible. Return one split with that maximum number of terms. If no valid split exists, return an empty list. Both the choice of terms and their order may vary among valid optimal answers.
```cpp
class Solution {
public:
vector<long long> maximumEvenSplit(long long finalSum);
};
```
### Examples
**Example 1:**
```text
finalSum = 20
Output: [2,4,6,8]
Explanation: Four terms sum to 20, and the five smallest distinct positive evens already sum to 30.
```
**Example 2:**
```text
finalSum = 9
Output: []
Explanation: A sum of even terms cannot be odd.
```
### Constraints
- `1 <= finalSum <= 10^10`.
### Clarifying Questions
All terms must be positive, even and pairwise distinct. Both term choices and their order can vary among valid optimal answers.
```hint Inspect the structure
What is the smallest sum achievable with k distinct positive even terms?
```
### What a Strong Answer Covers
- Return positive, even, pairwise distinct terms whose sum is exactly finalSum.
- Prove that no valid split can contain more terms than the returned one.
- Preserve every allowed optimum and handle inputs for which no split exists.
### Follow-up Questions
Can you determine the maximum possible number of terms before constructing a split?
Overview: Split a Sum into as Many Distinct Positive Evens as Possible. Return a list of distinct positive even integers summing to finalSum, using the largest possible number of terms. Return an empty list when no valid split exists. Any optimal split and any ordering of its terms are permitted.