LeetCode 2178 - Maximum Split of Positive Even Integers

The problem is asking us to take an input integer finalSum and split it into the maximum number of unique positive even integers such that their sum equals finalSum.

leetcodemediummathbacktrackinggreedy

LeetCode Problem 2178

Difficulty: 🟡 Medium
Topics: Math, Backtracking, Greedy

Solution

Problem Understanding

The problem is asking us to take an input integer finalSum and split it into the maximum number of unique positive even integers such that their sum equals finalSum. A unique positive even integer means each number in the split must be even, greater than zero, and cannot be repeated. If no valid split exists (for example, when finalSum is odd), we return an empty list.

The input finalSum ranges from 1 to 10^10, which means any solution must be efficient and cannot rely on brute-force exploration of all subsets. The output is a list of integers representing a split that maximizes the number of integers. Edge cases include when finalSum is odd (no valid split), when finalSum is very small (like 2), or when finalSum is just large enough to contain many small even numbers.

Approaches

The brute-force approach would attempt to generate all combinations of positive even integers and check which sums equal finalSum, then return the combination with the largest length. This works in theory but is computationally infeasible for large numbers because the number of combinations grows exponentially.

The key observation for an optimal solution is that to maximize the number of integers, we should start from the smallest possible positive even integer (2) and keep adding the next even number (4, 6, 8, ...) until the running sum exceeds or matches finalSum. If the running sum exceeds finalSum, we can adjust the last number in the split to compensate for the difference, ensuring the sum equals finalSum while keeping all numbers unique.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(2^(finalSum/2)) O(n) Generates all possible combinations of even numbers and checks sums
Optimal O(sqrt(finalSum)) O(sqrt(finalSum)) Greedy approach using consecutive even integers starting from 2

Algorithm Walkthrough

  1. Check if finalSum is odd. If it is, return an empty list immediately because no sum of even numbers can produce an odd total.
  2. Initialize an empty list split to store the numbers in the split.
  3. Start with the smallest positive even number 2 and a variable current to hold it.
  4. While finalSum is greater than or equal to current, append current to split and subtract it from finalSum. Then increment current by 2 to get the next even number.
  5. After the loop, if there is any leftover finalSum > 0, it represents the difference needed to reach the original target sum. Add this leftover to the last number in split to adjust the total sum while keeping all numbers unique.
  6. Return the list split.

Why it works: The greedy approach works because starting with the smallest even numbers maximizes the count of integers in the split. Adding the leftover to the last number maintains uniqueness while ensuring the total sum equals finalSum.

Python Solution

from typing import List

class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum % 2 != 0:
            return []
        
        split = []
        current = 2
        
        while finalSum >= current:
            split.append(current)
            finalSum -= current
            current += 2
        
        if finalSum > 0:
            split[-1] += finalSum
        
        return split

The code first checks if finalSum is odd and returns an empty list if so. It then uses a greedy loop to add consecutive even numbers to the split list. If any leftover remains, it is added to the last element to maintain the sum. The solution handles all valid edge cases efficiently.

Go Solution

func maximumEvenSplit(finalSum int64) []int64 {
    if finalSum%2 != 0 {
        return []int64{}
    }

    split := []int64{}
    current := int64(2)

    for finalSum >= current {
        split = append(split, current)
        finalSum -= current
        current += 2
    }

    if finalSum > 0 {
        split[len(split)-1] += finalSum
    }

    return split
}

In Go, the algorithm follows the same greedy strategy. We handle int64 for large sums. The slice split dynamically grows as we append even numbers. Any leftover finalSum is added to the last element to reach the exact target sum.

Worked Examples

Example 1: finalSum = 12

Iteration steps:

Current Split Remaining finalSum
2 [2] 10
4 [2,4] 6
6 [2,4,6] 0

No leftover, return [2,4,6].

Example 2: finalSum = 7

Since 7 is odd, return [].

Example 3: finalSum = 28

Iteration steps:

Current Split Remaining finalSum
2 [2] 26
4 [2,4] 22
6 [2,4,6] 16
8 [2,4,6,8] 8

Leftover is 8, add to last element: [2,4,6,16].

Complexity Analysis

Measure Complexity Explanation
Time O(sqrt(finalSum)) We iterate through consecutive even numbers up to approximately sqrt(finalSum) for the sum formula n(n+1) ≤ finalSum
Space O(sqrt(finalSum)) The split list stores each selected even integer, which is also O(sqrt(finalSum))

The reasoning comes from the fact that the sum of the first n even numbers is roughly quadratic, so the number of iterations scales with the square root of finalSum.

Test Cases

# Provided examples
assert Solution().maximumEvenSplit(12) == [2,4,6]  # max number of even integers
assert Solution().maximumEvenSplit(7) == []       # odd finalSum, no split
assert Solution().maximumEvenSplit(28) == [2,4,6,16]  # leftover added to last

# Edge and boundary cases
assert Solution().maximumEvenSplit(2) == [2]      # smallest even sum
assert Solution().maximumEvenSplit(1) == []       # smallest odd sum
assert Solution().maximumEvenSplit(100) == [2,4,6,8,10,12,14,16,28]  # large sum

# Large value
assert Solution().maximumEvenSplit(10**10)  # should run efficiently
Test Why
12 Valid split with max numbers
7 Odd sum, returns empty
28 Handles leftover addition
2 Smallest valid even number
1 Smallest invalid odd number
100 Ensures multiple consecutive numbers are used
10^10 Performance test for large input

Edge Cases

One important edge case is when finalSum is odd. No sum of positive even numbers can equal an odd number. The implementation immediately returns an empty list.

Another edge case is when finalSum is exactly one small even number, like 2. The greedy loop only runs once, correctly returning [2].

A third edge case is when finalSum is large and the leftover after adding consecutive numbers must be appended to the last element. The algorithm correctly handles this by adjusting the last number, ensuring uniqueness and correctness of the total sum.