Leetcode 2178: Maximum Split of Positive Even Integers

Input: The input consists of a single integer `finalSum`.

Example: 18

Constraints:

• 1 <= finalSum <= 10^10

Output: The output is a list of unique even integers that sum up to `finalSum`. If no valid split is possible, return an empty array.

Example: [2, 4, 6, 8]

Constraints:

• The integers must be positive, even, and unique.

Goal: The goal is to find the maximum number of unique positive even integers that sum up to `finalSum`.

Steps:

• Check if `finalSum` is even. If it is not, return an empty array.

• Start with the smallest even integer (2), and keep adding the next even integers (4, 6, 8, ...) until the sum exceeds `finalSum`.

• If there is any remaining sum, adjust the last integer in the list to make the total sum equal to `finalSum`.

Goal: The input `finalSum` should be within the given bounds.

Steps:

• 1 <= finalSum <= 10^10

Assumptions:

• The integer `finalSum` is positive.

• Input: 18

• Explanation: The number 18 can be expressed as the sum of four unique even integers: 2 + 4 + 6 + 8.

Approach: The approach involves adding consecutive even integers until the sum reaches or exceeds `finalSum`, and then adjusting the last integer if necessary.

Observations:

• The sum of unique positive even integers grows quickly, so we can stop once we reach or exceed `finalSum`.

• Start from the smallest even integer and continue adding consecutive even integers until the sum is close to `finalSum`.

Steps:

• Check if `finalSum` is even.

• Add consecutive even integers to the result list.

• If the sum exceeds `finalSum`, adjust the last integer to make the total sum equal to `finalSum`.

Empty Inputs:

• If `finalSum` is an odd number, return an empty list.

Large Inputs:

• Ensure the solution works efficiently for large inputs, up to 10^10.

Special Values:

• For very small values like `finalSum = 1`, the result should be an empty list since no even numbers can sum to 1.

Constraints:

• Ensure the solution handles large values of `finalSum` efficiently.

vector<long long> ans;
vector<long long> maximumEvenSplit(long long sum) {
    vector<long long> tmp;
    if(sum % 2 == 1) return ans;
    
    int cur = 2;
    while(sum >= cur) {
        ans.push_back(cur);
        sum -= cur;
        cur += 2;
    }
    if(sum > 0) ans[ans.size() - 1] += sum;
    
    return ans;
}

1 : Variable Initialization

vector<long long> ans;

Initialize an empty vector `ans` to store the result.

2 : Function Definition

vector<long long> maximumEvenSplit(long long sum) {

Define the function `maximumEvenSplit` that takes a long long integer `sum` and returns a vector of long long integers.

3 : Variable Initialization

    vector<long long> tmp;

Declare an unused vector `tmp`. This line doesn't impact the algorithm and could be removed.

4 : Condition Check

    if(sum % 2 == 1) return ans;

Check if `sum` is odd. If true, return the empty vector `ans`.

5 : Variable Initialization

    int cur = 2;

Initialize the variable `cur` to 2, which will be used to split the sum into even numbers.

6 : Loop

    while(sum >= cur) {

Start a while loop that continues as long as `sum` is greater than or equal to `cur`.

7 : Vector Modification

        ans.push_back(cur);

Push the current value of `cur` into the `ans` vector.

8 : Update Sum

        sum -= cur;

Reduce `sum` by the value of `cur`.

9 : Update Variable

        cur += 2;

Increase `cur` by 2 to maintain the even sequence (2, 4, 6, 8, ...).

10 : Final Adjustment

    if(sum > 0) ans[ans.size() - 1] += sum;

If there's any remaining `sum` (less than the next even number), add it to the last element of the `ans` vector.

11 : Return Statement

    return ans;

Return the `ans` vector, which contains the even splits of `sum`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear with respect to the number of integers required to reach `finalSum`.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is linear because we store the list of even integers.

Leetcode 2178: Maximum Split of Positive Even Integers

Explore →