You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.
finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.
Example 1:
Input: finalSum = 12 Output: [2,4,6] Explanation: The following are valid splits:(12),(2 + 10),(2 + 4 + 6), and(4 + 8). (2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6]. Note that [2,6,4], [6,2,4], etc. are also accepted.
Example 2:
Input: finalSum = 7 Output: [] Explanation: There are no valid splits for the given finalSum. Thus, we return an empty array.
Example 3:
Input: finalSum = 28 Output: [6,8,2,12] Explanation: The following are valid splits:(2 + 26),(6 + 8 + 2 + 12), and(4 + 24).(6 + 8 + 2 + 12)has the maximum number of integers, which is 4. Thus, we return [6,8,2,12]. Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.
Constraints:
1 <= finalSum <= 1010In #2178 Maximum Split of Positive Even Integers, the goal is to break a given even sum into the maximum number of distinct positive even integers. A key observation is that if the total sum is odd, no valid split exists because the sum of even numbers is always even.
A common strategy is a greedy approach. Instead of trying all combinations (which would lead to exponential complexity with backtracking), you gradually construct the split using the smallest possible even numbers such as 2, 4, 6, .... This maximizes the count of numbers in the result. As you add values, track the remaining sum and ensure all elements stay unique. If the remaining value would break the uniqueness constraint, you can merge the remainder into the last chosen number.
This approach avoids expensive enumeration and works efficiently because the sequence grows only until the partial sum approaches the target. The runtime is roughly proportional to the number of chosen even integers.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy incremental construction | O(k) | O(k) |
| Backtracking / enumeration | O(2^n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
First, check if finalSum is divisible by 2. If it isn’t, then we cannot split it into even integers.
Let k be the number of elements in our split. As we want the maximum number of elements, we should try to use the first k - 1 even elements to grow our sum as slowly as possible.
Thus, we find the maximum sum of the first k - 1 even elements which is less than finalSum.
We then add the difference over to the kth element.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this appear in technical interviews because they test mathematical reasoning and greedy thinking. Interviewers often expect candidates to move from brute force ideas to an optimized greedy approach.
The optimal approach uses a greedy strategy. Start forming the split using the smallest even numbers so you maximize the count of elements. If the remaining sum cannot form a new unique even number, you can adjust the last element by adding the remainder.
Using the smallest even numbers first ensures you create as many elements as possible while keeping them distinct. Larger numbers would reduce the total count of elements in the split. The greedy pattern naturally maximizes the number of integers.
A simple dynamic array or list is enough to store the chosen even integers. Since the values are added sequentially and only occasionally adjusted at the end, no complex data structures are required.