Maximum Split of Positive Even Integers

Medium
855.

Maximum Split of Positive Even Integers

Maximum Split of Positive Even Integers is a medium coding problem on math and greedy, asked in Amazon, Google and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} finalSum
 * @return {number[]}
 */
var maximumEvenSplit = function(finalSum) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Split of Positive Even Integers — Problem & Solution

Maximum Split of Positive Even Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Split of Positive Even Integers is a medium coding problem on math and greedy, asked in Amazon, Google and Zoho interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Maximum Split of Positive Even Integers

  1. Hint 1

    An odd finalSum is impossible — any sum of even numbers is even.

  2. Hint 2

    To maximise the count, take the smallest unused even numbers: 2, 4, 6, …

  3. Hint 3

    When the next number no longer fits, add whatever is left to the largest term already taken.

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

Java

public static int[] maximumEvenSplit(int finalSum) {
    if (finalSum % 2 != 0) return new int[0];
    List<Integer> out = new ArrayList<>();
    int rem = finalSum, i = 2;
    while (i <= rem) {
        out.add(i);
        rem -= i;
        i += 2;
    }
    out.set(out.size() - 1, out.get(out.size() - 1) + rem);
    int[] res = new int[out.size()];
    for (int k = 0; k < out.size(); k++) res[k] = out.get(k);
    return res;
}

C++

vector<int> maximumEvenSplit(int finalSum) {
    if (finalSum % 2 != 0) return vector<int>();
    vector<int> out;
    int rem = finalSum, i = 2;
    while (i <= rem) {
        out.push_back(i);
        rem -= i;
        i += 2;
    }
    out.back() += 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms