How hard is LeetCode 2178. Maximum Split of Positive Even Integers?

LeetCode 2178. Maximum Split of Positive Even Integers is rated Medium on LeetCode.

What is the time complexity of LeetCode 2178. Maximum Split of Positive Even Integers?

The Python solution on this page runs in O(\sqrt{\textit{finalSum}}), and ignoring the space consumption of the answer array, the space complexity is O(1).

What is the space complexity of LeetCode 2178. Maximum Split of Positive Even Integers?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2178. Maximum Split of Positive Even Integers cover?

LeetCode 2178. Maximum Split of Positive Even Integers is tagged Greedy, Math and Backtracking on LeetCode.

Maximum Split of Positive Even Integers — LeetCode 2178 Python Solution

MediumGreedyMathBacktracking

Problem: #2178
Pattern: Backtracking
Reading time: 2 min
Source: leetcode.com

The problem

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

Example

Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).

Python solution

Python

class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum & 1:
            return []
        ans = []
        i = 2
        while i <= finalSum:
            finalSum -= i
            ans.append(i)
            i += 2
        ans[-1] += finalSum
        return ans

Complexity

Measure	Complexity
Time	O(\sqrt{\textit{finalSum}}), and ignoring the space consumption of the answer array, the space complexity is O(1)
Space	O(1) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2178. Maximum Split of Positive Even Integers is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2178. Maximum Split of Positive Even Integers?: LeetCode 2178. Maximum Split of Positive Even Integers is rated Medium on LeetCode.
What is the time complexity of LeetCode 2178. Maximum Split of Positive Even Integers?: The Python solution on this page runs in O(\sqrt{\textit{finalSum}}), and ignoring the space consumption of the answer array, the space complexity is O(1).
What is the space complexity of LeetCode 2178. Maximum Split of Positive Even Integers?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2178. Maximum Split of Positive Even Integers cover?: LeetCode 2178. Maximum Split of Positive Even Integers is tagged Greedy, Math and Backtracking on LeetCode.