Skip to main content
Talentd

Maximum Split of Positive Even Integers - Solution & Explanation

MediumMathBacktrackingGreedy14 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer finalSum, return the maximum number of unique positive even integers whose sum equals that value. If finalSum is odd, no valid split exists. The challenge is constructing the largest set of distinct even numbers while keeping the total exactly equal to the target.

Approach 1: Recursive Divide and Conquer (Backtracking) (Time: O(2^n), Space: O(n))

This approach explores combinations of even numbers using recursion. Start from the smallest even number (2) and recursively decide whether to include the next even value in the split. The recursion tracks the remaining sum and the current list of chosen numbers. If the remaining value becomes zero, a valid split is found. Because the algorithm tries many combinations, the branching factor grows quickly and results in exponential time complexity. This method is useful for understanding the search space and practicing recursion with backtracking, but it is not efficient for large inputs.

Approach 2: Iterative Dynamic Programming (Time: O(n^2), Space: O(n))

Dynamic programming builds solutions for smaller sums and uses them to construct larger ones. Create a DP array where each index represents whether a sum can be formed using unique even numbers. For each even number 2, 4, 6..., update states by checking whether adding the current number creates a valid new sum. While this avoids exploring every recursive path, it still requires iterating through many possible states and combinations. The DP approach works well when you want to explicitly track achievable sums and demonstrate subset-style reasoning often used in dynamic programming problems.

Approach 3: Greedy Mathematical Construction (Time: O(sqrt(n)), Space: O(1) excluding output)

The optimal insight comes from greedy algorithms. To maximize the count of distinct even numbers, always take the smallest possible unused even integer. Start with 2, then 4, 6, and keep subtracting from finalSum. Once the remaining value becomes smaller than the next candidate even number, add the leftover to the last element in the list. This keeps all numbers unique while preserving the total sum. If finalSum is odd, return an empty list immediately. Because the sequence of even numbers grows linearly while their sum grows quadratically, the loop runs roughly sqrt(finalSum) times, making it extremely efficient.

Recommended for interviews: The greedy construction is the expected solution. It demonstrates mathematical reasoning and efficient use of the problem constraints. Discussing the recursive search first shows you understand the full solution space, but implementing the greedy approach proves you can identify the optimal strategy quickly.

Approach 1: Recursive Divide and Conquer

This approach involves breaking down the problem recursively into smaller subproblems, solving each subproblem independently, and combining their results. It leverages the divide and conquer paradigm which is efficient for many types of problems.

The recursive solution divides the array into two halves and solves each half independently. It then combines the results to form the final answer.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) for a balanced division.
Space Complexity: O(log n) due to recursion stack space.

Try this approach in the editor →

Approach 2: Iterative Dynamic Programming

This approach uses an iterative dynamic programming method where we compute results in a bottom-up manner. It's especially useful when recursion might lead to stack overflow and provides an iterative solution with the same logic.

Using a DP array, the cumulative results from the array calculation are stored iteratively. This prevents recursive stack overflow and uses previous results for new calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to the DP array.

Try this approach in the editor →

Approach 3: Greedy

If finalSum is odd, it cannot be split into the sum of several distinct positive even integers, so we directly return an empty array.

Otherwise, we can greedily split finalSum in the order of 2, 4, 6, cdots, until finalSum can no longer be split into a different positive even integer. At this point, we add the remaining finalSum to the last positive even integer.

The time complexity is O(\sqrt{finalSum}), and ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Divide and Conquer

Time Complexity: O(n log n) for a balanced division.
Space Complexity: O(log n) due to recursion stack space.

Iterative Dynamic Programming

Time Complexity: O(n)
Space Complexity: O(n) due to the DP array.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Divide and Conquer (Backtracking)O(2^n)O(n)When exploring all possible combinations or demonstrating recursion and search space exploration
Iterative Dynamic ProgrammingO(n^2)O(n)When modeling the problem as a subset-sum style DP and tracking reachable sums
Greedy Mathematical ConstructionO(sqrt(n))O(1)Best choice for production or interviews; constructs the maximum set directly

Video Solution

2178. Maximum Split of Positive Even Integers || Biweekly Contest 72 || Leetcode 2178 • Bro Coders • 1,919 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Split of Positive Even Integers easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Many candidates initially try backtracking or subset-sum style dynamic programming. Recognizing that choosing the smallest distinct even numbers maximizes the count leads to the optimal solution.
Maximum Split of Positive Even Integers Python/Java solution
Python and Java implementations typically follow the greedy pattern: check if the input is odd, iterate through even numbers starting from 2, subtract them from the remaining sum, and store them in a list. When the remaining value is smaller than the next even number, add the remainder to the last element to maintain uniqueness.
How to solve Maximum Split of Positive Even Integers in O(n)?
An efficient solution uses a greedy sequence of even numbers. Start from 2 and keep adding the next even integer while subtracting from the remaining sum. When the remaining value becomes smaller than the next candidate, add the leftover to the last element. This effectively runs in about O(sqrt(n)) time, which is even faster than linear for large inputs.
What is the best approach for Maximum Split of Positive Even Integers?
The greedy approach is the most efficient solution. Start adding the smallest even numbers (2, 4, 6, ...) until the remaining sum becomes smaller than the next candidate. Add the leftover value to the last number to maintain uniqueness. This method runs in about O(sqrt(n)) time and uses constant extra space.
Is Maximum Split of Positive Even Integers asked at Google/Amazon/Meta?
Problems involving greedy number construction and unique sum decomposition appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. The exact problem may vary, but the underlying pattern of greedy selection and mathematical reasoning is common.
What data structure is used in Maximum Split of Positive Even Integers?
The greedy solution mainly uses a dynamic list or array to store the selected even integers. No complex data structures are required because the algorithm simply generates numbers sequentially and adjusts the final element if a remainder exists.
What is the time complexity of Maximum Split of Positive Even Integers?
The optimal greedy solution runs in O(sqrt(n)) time because the sum of the first k even numbers grows roughly quadratically. Backtracking solutions can take O(2^n) time due to exploring combinations, while dynamic programming implementations typically require O(n^2) time.

Ready to solve this problem?

Practice Maximum Split of Positive Even Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer