Problem
You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.
For example, given 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 finalSumcannot 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 = 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.
Approach
From the intuition that using the smallest even numbers will be the ideal move, we can start off from 2, the smallest positive even number, then progress by adding 2 to each following integer.
At the end, if the sum of the even numbers up to the maximum index is less than the target sum, we can adjust the last even number to make the overall sum equal to the target sum.
This is a typical greedy approach, where once we find the intuition and show that is works, the actual problem would mostly not be algorithm-heavy.
Solution
def maximumEvenSplit(self, finalSum: int) -> List[int]:
curr = 2
res = []
if finalSum % 2: return res
while curr < finalSum:
finalSum -= curr
res.append(curr)
curr += 2
if finalSum not in res:
res.append(finalSum)
else: res[-1] += finalSum
return res