Maximum Split of Positive Even Integers - Practice Coding Problems

Maximum Split of Positive Even Integers - 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 a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

Input & Output

Example 1 — Basic Case

$ Input: finalSum = 12

› Output: [2,4,6]

💡 Note: We can split 12 into 2+4+6=12. This gives us 3 unique even integers, which is maximum possible. Other valid splits like (12) or (2,10) have fewer integers.

Example 2 — Small Sum

$ Input: finalSum = 7

› Output: []

💡 Note: Since 7 is odd, it cannot be expressed as a sum of even integers. Return empty array.

Example 3 — Single Number

$ Input: finalSum = 28

› Output: [2,4,6,16]

💡 Note: Start with 2,4,6,8,10... but 2+4+6+8+10=30>28. So we use [2,4,6] and remaining 28-12=16, giving [2,4,6,16].

Constraints

1 ≤ finalSum ≤ 10¹⁰

Visualization

Tap to expand

Understanding the Visualization

Input

Given finalSum = 12, need unique positive even integers

Process

Use greedy approach: start with smallest evens 2,4,6...

Output

Return [2,4,6] with maximum count of 3

Key Takeaway

🎯 Key Insight: Start with the smallest even numbers to maximize the count, using greedy approach for optimal O(√n) solution

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use a greedy approach starting with the smallest even numbers (2, 4, 6, 8...) to maximize the count. The optimal approach is the greedy method with O(√n) time complexity and O(√n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sequential Even Numbers	O(√n)	O(√n)	Start with smallest even numbers 2,4,6,8... and adjust the last one if needed
Brute Force - Try All Combinations	O(2^n)	O(2^n)	Generate all possible combinations of unique even numbers that sum to finalSum

Greedy - Sequential Even Numbers — Algorithm Steps

Start adding consecutive even numbers: 2, 4, 6, 8...
Continue until adding the next number would exceed finalSum
Adjust the last number to make the sum exactly finalSum
Return the result if all numbers remain positive and unique

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Sequential

Add 2, 4, 6, 8... while possible

Adjust Last

Set last number to remaining sum

Check Unique

Ensure all numbers are unique

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int finalSum, int* returnSize) {
    *returnSize = 0;
    if (finalSum % 2 == 1) {
        return NULL;
    }
    
    int* result = (int*)malloc(1000 * sizeof(int));
    int count = 0;
    int currentEven = 2;
    int remaining = finalSum;
    
    // Greedily add consecutive even numbers
    while (remaining > currentEven) {
        result[count++] = currentEven;
        remaining -= currentEven;
        currentEven += 2;
    }
    
    // Add the remaining amount as the last number
    if (remaining > 0) {
        result[count++] = remaining;
    }
    
    // Check if the last number is unique and even
    if (count > 1) {
        int lastNum = result[count - 1];
        for (int i = 0; i < count - 1; i++) {
            if (result[i] == lastNum) {
                // Merge last two numbers to maintain uniqueness
                int last = result[count - 1];
                count--;
                result[count - 1] += last;
                break;
            }
        }
    }
    
    *returnSize = count;
    return result;
}

int main() {
    int finalSum;
    scanf("%d", &finalSum);
    
    int returnSize;
    int* result = solution(finalSum, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

We add consecutive even numbers up to approximately √(finalSum), since sum of first k even numbers is k(k+1)

✓ Linear Growth

Space Complexity

O(√n)

Store at most √(finalSum) numbers in the result array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Sequential Even Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler