2178. Maximum Split of Positive Even Integers

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 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 33. 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 44. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

Constraints:

  • 11 \leq finalSum 1010\leq 10^{10}

Solution

Full Solution

First, let's think of how to determine if a sum SS can have a valid split that contains exactly KK integers.

The first case we should consider is whether or not a sum SS can have a valid split of any size. Since our split includes only even integers, SS will only have a split if it's even and we will return an empty list if SS is odd.

One observation we can make is that if some sum SS does have a valid split of KK integers, then a sum TT will also have a valid split of KK integers if TT is even and TST\geq S. Why is this true? Let's denote DD as the difference between TT and SS. From the split of KK integers from the sum SS, incrementing the largest integer in the split by DD results in a valid split of KK integers with a total sum of TT. It can be observed that increasing the greatest integer will always keep the entire list distinct.

Example

For this example, let's use the split 12=2+4+612 = 2 + 4 + 6 with S=12S = 12 and K=3K = 3. How will we construct a split of size KK with sum T=16T = 16?

First, we'll find the difference D=TS=4D = T - S = 4. Then, we'll add DD to the greatest integer in the split with sum SS, which is 66.

Thus, we obtain the split 16=2+4+1016 = 2 + 4 + 10 with sum TT and size KK.

Back to the Original Problem

We are given SS and asked to find the maximum possible KK and construct a split of size KK.

If we take the sum of the smallest KK positive even integers (2 + 4 + 6 + 8 + ... + 2*K), we'll obtain the least possible sum that has a split of size KK. Let's denote this sum as low. A sum SS will have a valid split of size KK if SS \geq low.

To solve the problem, we'll first find the maximum KK where SS \geq low. Starting with the split that sums to low, we'll add SS - low to the largest integer to obtain our final split for SS.

Simulation

Simulation

Time Complexity

For a sum SS with a split of maximum size KK, low = 2 + 4 + 6 + 8 + ... + 2*k. In the sum, there are O(K)O(K) elements and the average element is O(K)O(K), resulting in S=O(K2)S = O(K^2) and K=O(S)K = O(\sqrt{S}). Since our algorithm runs in O(K)O(K), our final time complexity is O(S)O(\sqrt{S}).

Time Complexity: O(S)O(\sqrt{S})

Space Complexity

Since we construct a list of size KK, our space complexity is also O(S)O(\sqrt{S}).

Space Complexity: O(S)O(\sqrt{S})

C++ Solution

1class Solution {
2   public:
3    vector<long long> maximumEvenSplit(long long finalSum) {
4        vector<long long> ans;    // integers in our split
5        if (finalSum % 2 == 1) {  // odd sum provides no solution
6            return ans;
7        }
8        long long currentSum = 0;  // keep track of the value of low
9        int i = 1;
10        while (currentSum + 2 * i <=
11               finalSum) {  // keep increasing size of split until maximum
12            currentSum += 2 * i;
13            ans.push_back(2 * i);
14            i++;
15        }
16        ans[ans.size() - 1] +=
17            finalSum - currentSum;  // add S - low to largest element
18        return ans;
19    }
20};

Java Solution

1class Solution {
2    public List<Long> maximumEvenSplit(long finalSum) {
3        List<Long> ans = new ArrayList<Long>(); // integers in our split
4        if (finalSum % 2 == 1) { // odd sum provides no solution
5            return ans;
6        }
7        long currentSum = 0; // keep track of the value of low
8        int i = 1;
9        while (currentSum + 2 * i
10            <= finalSum) { // keep increasing size of split until maximum
11            currentSum += 2 * i;
12            ans.add((long) 2 * i);
13            i++;
14        }
15        int idx = ans.size() - 1;
16        ans.set(idx,
17            ans.get(idx) + finalSum
18                - currentSum); // add S - low to largest element
19        return ans;
20    }
21}

Python Solution

1class Solution:
2    def maximumEvenSplit(self, finalSum: int) -> List[int]:
3        ans = []  # integers in our split
4        if finalSum % 2 == 1:  # odd sum provides no solution
5            return ans
6        currentSum = 0
7        i = 1
8        while (
9            currentSum + 2 * i <= finalSum
10        ):  # keep increasing size of split until maximum
11            currentSum += 2 * i
12            ans.append(2 * i)
13            i += 1
14        ans[len(ans) - 1] += finalSum - currentSum  # add S - low to largest element
15        return ans
16

Javascript Solution

1/**
2 * @param {number} finalSum
3 * @return {number[]}
4 */
5var maximumEvenSplit = function (finalSum) {
6  let ans = []; // integers in our split
7  if (finalSum % 2 === 1) {
8    // odd sum provides no solution
9    return ans;
10  }
11  let currentSum = 0; // keep track of the value of low
12  let i = 1;
13  while (currentSum + 2 * i <= finalSum) {
14    // keep increasing size of split until maximum
15    currentSum += 2 * i;
16    ans.push(2 * i);
17    i++;
18  }
19  ans[ans.length - 1] += finalSum - currentSum; // add S - low to largest element
20  return ans;
21};

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫