Maximum Split of Positive Even Integers

medium math greedy backtracking

Problem

Given an integer finalSum, split it into a sum of the maximum number of unique positive even integers. Return any one such split as a list, or an empty list if no valid split exists (which happens exactly when finalSum is odd).

InputfinalSum = 12

Output[2, 4, 6]

Valid splits include (12), (2+10), (2+4+6), (4+8). (2+4+6) uses the most terms — 3 — so it wins.

finalSum (1 .. 10^10)

def maximumEvenSplit(finalSum):
    # An odd total can never be a sum of even numbers.
    if finalSum % 2 != 0:
        return []
    result = []
    i = 2                      # smallest unused even number
    while i <= finalSum:
        result.append(i)       # greedily take the next even number
        finalSum -= i          # spend it from the remaining total
        i += 2                 # advance to the next even number
    # Whatever is left is even; fold it into the largest term
    # so every value stays unique and even.
    result[-1] += finalSum
    return result

function maximumEvenSplit(finalSum) {
  // An odd total can never be a sum of even numbers.
  if (finalSum % 2 !== 0) return [];
  const result = [];
  let i = 2;                   // smallest unused even number
  while (i <= finalSum) {
    result.push(i);            // greedily take the next even number
    finalSum -= i;             // spend it from the remaining total
    i += 2;                    // advance to the next even number
  }
  // Whatever is left is even; fold it into the largest term
  // so every value stays unique and even.
  result[result.length - 1] += finalSum;
  return result;
}

List<Long> maximumEvenSplit(long finalSum) {
    List<Long> result = new ArrayList<>();
    // An odd total can never be a sum of even numbers.
    if (finalSum % 2 != 0) return result;
    long i = 2;                  // smallest unused even number
    while (i <= finalSum) {
        result.add(i);           // greedily take the next even number
        finalSum -= i;           // spend it from the remaining total
        i += 2;                  // advance to the next even number
    }
    // Fold the leftover into the largest term to keep values unique.
    int last = result.size() - 1;
    result.set(last, result.get(last) + finalSum);
    return result;
}

vector<long long> maximumEvenSplit(long long finalSum) {
    vector<long long> result;
    // An odd total can never be a sum of even numbers.
    if (finalSum % 2 != 0) return result;
    long long i = 2;             // smallest unused even number
    while (i <= finalSum) {
        result.push_back(i);     // greedily take the next even number
        finalSum -= i;           // spend it from the remaining total
        i += 2;                  // advance to the next even number
    }
    // Fold the leftover into the largest term to keep values unique.
    result.back() += finalSum;
    return result;
}

Explanation

To pack in the most unique even numbers, each one we pick should be as small as possible. So we greedily take 2, 4, 6, 8, … in order, stopping the moment the next even number would exceed what is still left of finalSum.

The loop condition i <= finalSum guarantees that after taking i, the remaining amount never goes negative. We keep a running finalSum that shrinks as we spend each value.

When the loop ends there may be a small leftover. Because both finalSum and every value we subtracted were even, the leftover is also even. Adding it to the largest term keeps all values distinct (the last term only grows, so it can never collide with a smaller one) and keeps the count maximal.

If finalSum is odd, no sum of even numbers can ever reach it, so we return an empty list right away.

Example: finalSum = 28 → take 2, 4, 6, 8 (remaining 8), then 10 is too big, so fold 8 into the last term: [2, 4, 6, 16] — 4 terms.

Time: O(√finalSum) Space: O(√finalSum)