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 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 amaximum number of integers. If no valid split exists for finalSum, return anempty list. You may return the integers in any order.

Examples

Example 1

1
2
3
4
5
6
7
8
9


    
    
    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

1
2
3
4
5
6
7
8


    
    
    Input: finalSum = 7
    Output: []
    Explanation: There are no valid splits for the given finalSum.
    Thus, we return an empty array.

Example 3

1
2
3
4
5
6
7
8
9


    
    
    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 <= 1010

Solution

Method 1 – Greedy Construction

Intuition

To maximize the number of unique positive even integers that sum to finalSum, we should always pick the smallest available even number at each step. If the sum overshoots, we can adjust the last number to make the total match finalSum.

Approach

  1. If finalSum is odd, return an empty list (no solution).
  2. Start from 2 and keep adding the next even number to the answer list as long as the sum does not exceed finalSum.
  3. If the next even number would overshoot, add the remaining difference to the last number in the list to reach exactly finalSum.
  4. Return the constructed list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> ans;
        if (finalSum % 2) return ans;
        long long x = 2, sum = 0;
        while (sum + x <= finalSum) {
            ans.push_back(x);
            sum += x;
            x += 2;
        }
        if (sum < finalSum && !ans.empty())
            ans.back() += finalSum - sum;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func maximumEvenSplit(finalSum int64) []int64 {
    if finalSum%2 != 0 {
        return []int64{}
    }
    var ans []int64
    x, sum := int64(2), int64(0)
    for sum+x <= finalSum {
        ans = append(ans, x)
        sum += x
        x += 2
    }
    if sum < finalSum && len(ans) > 0 {
        ans[len(ans)-1] += finalSum - sum
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> ans = new ArrayList<>();
        if (finalSum % 2 != 0) return ans;
        long x = 2, sum = 0;
        while (sum + x <= finalSum) {
            ans.add(x);
            sum += x;
            x += 2;
        }
        if (sum < finalSum && !ans.isEmpty())
            ans.set(ans.size()-1, ans.get(ans.size()-1) + finalSum - sum);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maximumEvenSplit(finalSum: Long): List<Long> {
        if (finalSum % 2L != 0L) return emptyList()
        val ans = mutableListOf<Long>()
        var x = 2L; var sum = 0L
        while (sum + x <= finalSum) {
            ans.add(x)
            sum += x
            x += 2
        }
        if (sum < finalSum && ans.isNotEmpty())
            ans[ans.lastIndex] += finalSum - sum
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maximumEvenSplit(self, finalSum: int) -> list[int]:
        if finalSum % 2:
            return []
        ans: list[int] = []
        x, s = 2, 0
        while s + x <= finalSum:
            ans.append(x)
            s += x
            x += 2
        if s < finalSum and ans:
            ans[-1] += finalSum - s
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximum_even_split(final_sum: i64) -> Vec<i64> {
        if final_sum % 2 != 0 { return vec![]; }
        let mut ans = vec![];
        let (mut x, mut sum) = (2, 0);
        while sum + x <= final_sum {
            ans.push(x);
            sum += x;
            x += 2;
        }
        if sum < final_sum && !ans.is_empty() {
            *ans.last_mut().unwrap() += final_sum - sum;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumEvenSplit(finalSum: number): number[] {
        if (finalSum % 2 !== 0) return [];
        const ans: number[] = [];
        let x = 2, sum = 0;
        while (sum + x <= finalSum) {
            ans.push(x);
            sum += x;
            x += 2;
        }
        if (sum < finalSum && ans.length > 0)
            ans[ans.length - 1] += finalSum - sum;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(√finalSum), since the sum of the first k even numbers is O(k²), so the loop runs O(√finalSum) times.
  • 🧺 Space complexity: O(√finalSum), for the answer list.