Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2178.html
2178. Maximum Split of Positive Even Integers (Medium)
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 tofinalSum
):(2 + 10)
,(2 + 4 + 6)
, and(4 + 8)
. Among them,(2 + 4 + 6)
contains the maximum number of integers. Note thatfinalSum
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 some valid splits:(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 some 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 1. Backtracking
If finalSum
is odd, return empty array.
Otherwise, we keep trying subtracting 2, 4, 6, 8, ...
from finalSum
via backtracking.
-
// OJ: https://leetcode.com/problems/maximum-split-of-positive-even-integers/ // Time: O(sqrt(N)) // Space: O(sqrt(N)) class Solution { public: vector<long long> maximumEvenSplit(long long s) { if (s % 2) return {}; vector<long long> ans; function<bool(long, long)>dfs = [&](long i, long target) { if (target == 0) return true; if (target < i) return false; ans.push_back(i); if (dfs(i + 2, target - i)) return true; // use `i` ans.pop_back(); return dfs(i + 2, target); // skip `i` }; dfs(2, s); return ans; } };
-
class Solution: def maximumEvenSplit(self, finalSum: int) -> List[int]: if finalSum % 2: return [] i = 2 ans = [] while i <= finalSum: ans.append(i) finalSum -= i i += 2 ans[-1] += finalSum return ans ############ # 2178. Maximum Split of Positive Even Integers # https://leetcode.com/problems/maximum-split-of-positive-even-integers/ class Solution: def maximumEvenSplit(self, s: int) -> List[int]: if s & 1: return [] res = [] x = 2 while x <= s: res.append(x) s -= x x += 2 res[-1] += s return res
-
class Solution { public List<Long> maximumEvenSplit(long finalSum) { List<Long> ans = new ArrayList<>(); if (finalSum % 2 == 1) { return ans; } for (long i = 2; i <= finalSum; i += 2) { ans.add(i); finalSum -= i; } ans.add(ans.remove(ans.size() - 1) + finalSum); return ans; } }
-
func maximumEvenSplit(finalSum int64) []int64 { ans := []int64{} if finalSum%2 == 1 { return ans } for i := int64(2); i <= finalSum; i += 2 { ans = append(ans, i) finalSum -= i } ans[len(ans)-1] += finalSum return ans }
-
function maximumEvenSplit(finalSum: number): number[] { const ans: number[] = []; if (finalSum % 2 === 1) { return ans; } for (let i = 2; i <= finalSum; i += 2) { ans.push(i); finalSum -= i; } ans[ans.length - 1] += finalSum; return ans; }
-
public class Solution { public IList<long> MaximumEvenSplit(long finalSum) { IList<long> ans = new List<long>(); if (finalSum % 2 == 1) { return ans; } for (long i = 2; i <= finalSum; i += 2) { ans.Add(i); finalSum -= i; } ans[ans.Count - 1] += finalSum; return ans; } }
Solution 2. Greedy
In solution 1, in fact we only backtrack at most once.
We can keep trying subtracting 2, 4, 6, 8, ...
from finalSum
. We stop the loop when subtracting the current number i
is invalid – s - i < i + 2
(the reminder after the subtraction is less than the next even number). And we push the reminder into the answer.
-
// OJ: https://leetcode.com/problems/maximum-split-of-positive-even-integers/ // Time: O(sqrt(N)) // Space: O(1) class Solution { public: vector<long long> maximumEvenSplit(long long s) { if (s % 2) return {}; vector<long long> ans; for (int i = 2; s - i >= i + 2; i += 2) { ans.push_back(i); s -= i; } ans.push_back(s); return ans; } };
-
class Solution: def maximumEvenSplit(self, finalSum: int) -> List[int]: if finalSum % 2: return [] i = 2 ans = [] while i <= finalSum: ans.append(i) finalSum -= i i += 2 ans[-1] += finalSum return ans ############ # 2178. Maximum Split of Positive Even Integers # https://leetcode.com/problems/maximum-split-of-positive-even-integers/ class Solution: def maximumEvenSplit(self, s: int) -> List[int]: if s & 1: return [] res = [] x = 2 while x <= s: res.append(x) s -= x x += 2 res[-1] += s return res
-
class Solution { public List<Long> maximumEvenSplit(long finalSum) { List<Long> ans = new ArrayList<>(); if (finalSum % 2 == 1) { return ans; } for (long i = 2; i <= finalSum; i += 2) { ans.add(i); finalSum -= i; } ans.add(ans.remove(ans.size() - 1) + finalSum); return ans; } }
-
func maximumEvenSplit(finalSum int64) []int64 { ans := []int64{} if finalSum%2 == 1 { return ans } for i := int64(2); i <= finalSum; i += 2 { ans = append(ans, i) finalSum -= i } ans[len(ans)-1] += finalSum return ans }
-
function maximumEvenSplit(finalSum: number): number[] { const ans: number[] = []; if (finalSum % 2 === 1) { return ans; } for (let i = 2; i <= finalSum; i += 2) { ans.push(i); finalSum -= i; } ans[ans.length - 1] += finalSum; return ans; }
-
public class Solution { public IList<long> MaximumEvenSplit(long finalSum) { IList<long> ans = new List<long>(); if (finalSum % 2 == 1) { return ans; } for (long i = 2; i <= finalSum; i += 2) { ans.Add(i); finalSum -= i; } ans[ans.Count - 1] += finalSum; return ans; } }
Discuss
https://leetcode.com/problems/maximum-split-of-positive-even-integers/discuss/1783586