Introduction

This was a task at a university project, where I was the only one to solve it with a time complexity of O(N).

Objective

Problem

We are given an initial set set_a, which contains N natural numbers, and the task is to partition this set into two subsets, set_b and set_c, while following a specific set of rules:

1. Every element in set_b must be smaller than every element in set_c.
2. The sum of all elements in set_b should be equal to the sum of all elements in set_c if possible.
3. If achieving equal sums is not possible, the sum of set_b should be greater than the sum of set_c.
4. If set_a contains only the element 0, then set_b should contain 0 and set_c should be empty.

The key objective is to solve this problem with a time complexity of O(N), where N is the number of elements in set_a.

Assumptions

• The set set_a is sorted in ascending order and contains no duplicates.
• The helper function *set_max(Element result, Set s) finds the maximum element in set_a with a time complexity of O(1), as it simply accesses the last element in the sorted set.

Algorithm

void set_partition (Set * b, Set * c, Set a) {
    unsigned int sum_b = 0; unsigned int sum_c = 0; unsigned int max = 0;
    
    // Condition to prevent the case of set_a being empty
    if (set_max(&max, a) == 1) {
        int down = 0;
        int number = -1;

        // Time Complexity: O(N) : N = Size of the Set
        // Iterate through all elements
        for (int i = max - 1; i >= 0; i--) {

            // Decide what element to take
            // If sum_b is smaller than sum_c + max keep adding elements to sum_b
            // considering the second rule of the objective
            number = sum_b < sum_c + max ? down++ : down + i;
            
            // Because of implementation details of the set-type, 
            // it needs to be checked if the set contains the current number
            if (set_contains(a, number)) {
                if (number > down) {
                    // inserting the current highest number
                    set_insert(c, max);
                    sum_c += max;
                    max = number;
                } else {
                    // inserting in ascending order
                    set_insert(b, number);
                    sum_b += number;
                }
            }
        }
        // Last step, insert the last found maximum
        set_insert((sum_b >= sum_c + max && max != 0) ? c : b, max);
    }
}

Explanation

Here’s how the algorithm works:

Step 1: Initial Setup

• We initialize two variables, sum_b and sum_c, which will store the sum of elements in set_b and set_c respectively. Both are initialized to 0.
• We find the maximum value in set_a and store it in the max variable using the set_max() function.

If set_a contains only 0, the algorithm directly inserts 0 into set_b and leaves set_c empty, satisfying the fourth rule of the problem.

Step 2: Iterating Through the Set

The core of the algorithm is a loop that starts from the second-largest element (i.e., max - 1) and works its way down to the smallest element. The goal is to decide which subset (set_b or set_c) each element should be added to, while maintaining the sum conditions.

During each iteration, the algorithm checks whether the sum of set_b is smaller than the sum of set_c plus the current maximum element (sum_c + max). Based on this comparison, it assigns the next smallest element (starting from the smallest) to set_b or set_c as follows:

• If sum_b < sum_c + max: The algorithm assigns the next smallest available element to set_b.
• Otherwise: The algorithm assigns the next smallest available element to set_c.

Step 3: Inserting Elements from Top and Bottom

• The algorithm continues to assign elements to either set_b or set_c until all elements from set_a (except the maximum element) have been assigned. This process ensures that the sums of the two sets are as close as possible to each other.
• The algorithm uses a greedy approach by inserting elements in a way that attempts to equalize the sums of set_b and set_c.

Step 4: Final Insertion of the Maximum Element

Once the loop completes, the algorithm performs one final check: it decides which subset the maximum element should be inserted into, based on the sums of set_b and set_c.

• If sum_b is greater than or equal to sum_c + max, the maximum element is inserted into set_b.
• Otherwise, the maximum element is inserted into set_c.

This final step ensures that the partitioning adheres to the rules outlined earlier.

ELI5

We have the initial set_a that is an ordered set with all our elements. We start from the maximum value and keep it mind.

Now we start iterating through all the other numbers, we can decide for each iteration whether to take from the smallest or highest number of the remaining elements.

We keep inserting our elements in each iteration into set_b until it is larger than set_c + maximum. Once this happens we know that the maximum can now be inserted into set_c, because it won't break any of the rules.