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

Tug of War


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  Longest Subarray Having Count of 1s One More than Count of 0s

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
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup