Home » Technical Interview Questions » Array Interview Questions » Tug of War

Tug of War


Reading Time - 4 mins


Difficulty Level Hard

In tug of war problem, we have given an array of integers, divide the array into two subsets of size n/2 size each so that the difference of the sum of two subsets is as minimum as possible. If n is even each subset size is n/2. If n is odd one subset size must be n-1/2 and the size of another is n+1/2. The Sum of elements of both subsets should have approximately the same sum.

Example

Input

arr[] = {1, 4, 7, -3, 15, 11, 14, 13, 10, 8}

Output

subset1: [4, 7, 8, 11, 13]
subset2: [10, 14, 6, 15, -3]

Explanation

Here, size is 10(even) each array should be of length 5
(4 + 7 + 8 + 11 + 13) – (10 + 14 + 6 + 15 + -3) = 0, minimum difference.

Input

arr[] = {-1, -3, -5, -6, 4, 11, 17, 23, 27, 19}

Output

subset1: [23, 17, -6, 4]
subset2: [27, -1, -3, 19, -5]

Explanation

Here, size is 9(odd),one array size is 5 and other will be 4.
(23 + 17 + -6 + 4) – (27 + -1 + -3 + 19 + -5) = -1

Algorithm of Tug of War

Try every subset of half size and compare it with the remaining half.

a. We initialize the current set as an empty set and add elements one by one.

b. For all the elements it should be part of the current set or part of the remaining set.

c. For the current set becomes n/2, we check whether this solution is better than the best solution available until that point.

READ  Minimum Size Subarray Sum

d. Update if it is the best solution. Print the final solution.

C++ Program of Tug of War

#include <iostream>
#include <stdlib.h>
#include <limits.h>

using namespace std;
 

void TugofWarRecur(int* array, int n, bool* current_elements, int selected_elements_count,bool* solution, int* min_diff, int sum, int current_sum, int current_position)
{
    
    if (current_position == n)
    {
        return;
    }
    if ((n/2 - selected_elements_count) > (n - current_position))
    {
        return;
    }
 
    TugofWarRecur(array, n, current_elements, selected_elements_count,solution, min_diff, sum, current_sum, current_position+1);
 
    selected_elements_count++;
    current_sum = current_sum + array[current_position];
    current_elements[current_position] = true;
    if (selected_elements_count == n/2)
    {
        if (abs(sum/2 - current_sum) < *min_diff)
        {
            *min_diff = abs(sum/2 - current_sum);
            for (int i = 0; i<n; i++)
            {
                solution[i] = current_elements[i];
            }
        }
    }
    else
    {
        TugofWarRecur(array, n, current_elements, selected_elements_count, solution, min_diff, sum, current_sum, current_position+1);
    }
    current_elements[current_position] = false;
}
 
void TugOfWar(int *array, int n)
{
    bool* current_elements = new bool[n];
    bool* solution = new bool[n];
    int min_diff = INT_MAX;
    int sum = 0;
    for (int i=0; i<n; i++)
    {
        sum =sum + array[i];
        current_elements[i] =  solution[i] = false;
    }
    TugofWarRecur(array, n, current_elements, 0, solution, &min_diff, sum, 0, 0);
 
    cout << "subset 1: ";
    for (int i=0; i<n; i++)
    {
        if(solution[i] == true)
        {
            cout << array[i] << " ";
        }
    }
    cout << "\nsubset 2: ";
    for (int i=0; i<n; i++)
    {
        if(solution[i] == false)
        {
            cout << array[i] << " ";
        }
    }
}
 
//Main function
int main()
{
    int input_array[] = {1, 4, 7, -3, 15, 11, 14, 13, 10, 8};
    int size = sizeof(input_array)/sizeof(input_array[0]);
    TugOfWar(input_array,size);
    return 0;
}
subset 1: -3 11 14 10 8 
subset 2: 1 4 7 15 13

Complexity Analysis of Tug of War

Time Complexity

O(n^2) where n is the number of elements present in the array. If the size of subset n is even, it must be divided into n/2, but for the odd value of n, then the size of one subset must be (n-1)/2, and size of another subset must be (n+1)/2.

READ  Find minimum difference between any two elements

Space Complexity

O(1) because we dont use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions