Leetcode

Maximum Split of Positive Even Integers

May 26, 2022 by aAshish

  • Time:O(\sqrt \texttt{finalSum})
  • Space:O(\sqrt \texttt{finalSum})

C++

 
class Solution {
 public:
  vector<long long> maximumEvenSplit(long long finalSum) {
    if (finalSum & 1)
      return {};

    vector<long long> ans;
    long long needSum = finalSum;
    long long even = 2;

    while (needSum - even >= even + 2) {
      ans.push_back(even);
      needSum -= even;
      even += 2;
    }

    ans.push_back(needSum);
    return ans;
  }
};

JAVA

 
class Solution {
  public List<Long> maximumEvenSplit(long finalSum) {
    if (finalSum % 2 == 1)
      return new ArrayList<>();

    List<Long> ans = new ArrayList<>();
    long needSum = finalSum;
    long even = 2;

    while (needSum - even >= even + 2) {
      ans.add(even);
      needSum -= even;
      even += 2;
    }

    ans.add(needSum);
    return ans;
  }
}

Python

 
class Solution:
  def maximumEvenSplit(self, finalSum: int) -> List[int]:
    if finalSum & 1:
      return []

    ans = []
    needSum = finalSum
    even = 2

    while needSum - even >= even + 2:
      ans.append(even)
      needSum -= even
      even += 2

    return ans + [needSum]