Maximum Split of Positive Even Integers — Medium Problem & Solution

Problem statement

Split finalSum into the maximum number of unique positive even integers that add up to it, and return them in increasing order.

If no such split exists, return an empty array.

Example 1

Input: finalSum = 12
Output: [2,4,6]
Explanation: Three distinct even numbers; no split into four exists.

Example 2

Input: finalSum = 7
Output: []
Explanation: An odd total can never be a sum of even numbers.

Example 3

Input: finalSum = 28
Output: [2,4,6,16]
Explanation: The greedy takes 2, 4, 6 and 8 and then folds the leftover 8 into the last term.

Constraints

• 1 <= finalSum <= 1000000000

How to solve Maximum Split of Positive Even Integers

Take the smallest even numbers in order for as long as they fit; the leftover is then folded into the last term, which keeps the values distinct and the count maximal.

Approach

1. Return empty for an odd finalSum.
2. Take 2, 4, 6, … while the next value is at most the remaining total.
3. Add the remaining total to the last value taken.

Why it works

Greedily taking the smallest available even numbers maximises how many fit — using any larger value instead would consume budget that could have supported more terms. The leftover after stopping is even and strictly smaller than the next unused value, so adding it to the last term keeps that term the largest and still distinct from all the others.

Complexity

• Time — O(sqrt(finalSum))
• Space — O(sqrt(finalSum))

Pitfalls

• Appending the leftover as a new term can duplicate a value already taken.
• The odd case must be handled before the loop.
• The greedy takes 2 · k terms up to roughly sqrt(finalSum), so the output stays small.

Reference solution

Python

from typing import List

def maximumEvenSplit(finalSum: int) -> List[int]:
    if finalSum % 2 != 0:
        return []
    out = []
    rem, i = finalSum, 2
    while i <= rem:
        out.append(i)
        rem -= i
        i += 2
    out[-1] += rem
    return out

JavaScript

var maximumEvenSplit = function(finalSum) {
    if (finalSum % 2 !== 0) return [];
    var out = [];
    var rem = finalSum, i = 2;
    while (i <= rem) { out.push(i); rem -= i; i += 2; }
    out[out.length - 1] += rem;
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium