Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the subsequence?
3.2.
What is a boolean array?
3.3.
Difference b/w recursion and backtracking?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Tug Of War

Author Harsh Goyal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM
DSA Problems

Introduction 

This blog will discuss the approach to solving the Tug off war problemBefore jumping into the approach to solving the tug of war problem, let’s first understand what is the tug of war problem, in this problem, we need to divide our array into two subsequences or we can say two subsets in such a way, that the difference between both the calculated sum of both the subsequence will be as minimum as possible.

Note: In this tug of war problem, if the size of the array is even, then, the size of the two subsequences will be half the size of the array, but if the size of the array is odd, then, the size of the first subsequence is the (size - 1) / 2 and the size of the second subsequence is the (size + 1) / 2.

Sample Example

Input:-

15

10

20

8

12

18

25

 

Output:- 

First subsequence

12

18

25

Second subsequence

15

10

20

8

 

Explanation:-

After checking each possible combination, the best-suited 2 subsequences are:

  • 12 , 18 , 25
  • 15, 10, 20, 8

 

The sum of all the elements of the first subsequence is 55, whereas the sum of the second subsequence is 53, and the difference between both the sums is only 2 which is the minimum, therefore these two are the resultant subsequences.

You can try this problem in Coding Ninjas Studio using this link.

Also see, Data Structures

Approach

In this tug of war problem, we have to check each possible subsequence of half the size of the input array, and, the other subsequence will be formed by the remaining elements. We will consider the position of each element in the respective subsequence using the boolean array. In the process, if the size of the current subsequence is equal to half the size of the input array, then, we have to check whether the best solution is available or not.

Steps of Algorithm

Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one vector of integer ‘input’ and the second is the size of that vector.

Step 2. In this ‘getResult()’ function, we need to initialize two boolean arrays named ‘temp’ and ‘res’ and two integer variables named ‘mini’ and ‘sum’.

Step 3. Make an iteration using the ‘for’ loop with the help of the ‘i’ variable to assign the collective total of all the input elements to ‘sum’ and assign a ‘false’ value to both the boolean arrays ‘temp’ and ‘res’.

Step 4. Create a function ‘helper’ that will accept nine parameters, i.e., one vector of integer ‘input’, second is the size of the vector, third is the boolean array ‘temp’, fourth is the zero which will depict the total number of selected elements, the fifth is another boolean array ‘res’, sixth is the integer variable ‘mini’, seventh is the integer variable ‘sum’, eight is the integer variable ‘curr_sum’ and ninth is the integer variable ‘cur_Index + 1’

Step 5. In this ‘helper’ function, Increment the value of ‘selected’ and add the value of the element at ‘cur_Index’ of ‘input’ to ‘cur_sum’ and assign ‘true’ value to element at ‘cur_Index’ of ‘temp’.

Step 6. Check if the value of ‘selected’ is equal to half the value of the size of the vector or not,

  • If it is equal then, check for the best solution by checking if the absolute value of the difference of ‘sum / 2’ and ‘curr_sum’ is less than ‘mini’ or not, if it is less than the value of ‘mini’, then assign that value to ‘mini’ and assign the complete ‘temp’ array to ‘res’ array using ‘for’ loop.
  • Else, make a recursive call using the ‘helper’ function with updating the parameters as shown in the code.

Step 7. Assign ‘false’ value to the element at ‘cur_Index’ of ‘temp’ boolean array.

Step 8. Print both the subsequence.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Check all the valid options using this helper function
void helper(vector<int> input, int n, bool* temp, int selected, bool* res, int* mini, int sum, int curr_sum, int cur_Index)
{
   // Edge case
   if (cur_Index == n)
       return;

   // Check the size
   if ((n/2 - selected) > (n - cur_Index))
       return;

   // Case when current element is not considered in the result
   helper(input, n, temp, selected, res, mini, sum, curr_sum, cur_Index + 1);

   selected++;
   curr_sum = curr_sum + input[cur_Index];
   temp[cur_Index] = true;

   // checks if a solution is formed
   if (selected == n / 2)
   {
       // check for the best solution
       if (abs(sum / 2 - curr_sum) < *mini)
       {
           *mini = abs(sum/2 - curr_sum);
           for (int i = 0; i<n; i++)
               res[i] = temp[i];
       }
   }
   else
   {
       // Case when current element is considered in the result
       helper(input, n, temp, selected, res, mini, sum, curr_sum, cur_Index + 1);
   }

   temp[cur_Index] = false;
}

// main function that generate an arr
void getResult(vector<int> input, int n)
{
   bool* temp = new bool[n];

   bool* res = new bool[n];

   int mini = INT_MAX;

   int sum = 0;

   // Compute sum
   for (int i = 0; i < n; i++)
   {
       sum += input[i];
       temp[i] = res[i] = false;
   }

   // Recursive call to helper
   helper(input, n, temp, 0, res, &mini, sum, 0, 0);

   // Print both the subsequence
   cout << "The first subsequence: ";
   for (int i = 0; i<n; i++)
   {
       if (res[i] == true)
           cout << input[i] << ", ";
   }
   cout << endl;
   cout << "The second subsequence: ";
   for (int i = 0; i < n; i++)
   {
       if (res[i] == false)
           cout << input[i] << ", ";
   }
}

int main()
{
   // Input array
   vector<int> input = {15, 10, 20, 8, 12, 18, 25};
   int n = input.size();
   getResult(input, n);
   return 0;
}

 

Output:

The first subsequence: 12, 18, 25, 
The second subsequence: 15, 10, 20, 8,

 

Complexity Analysis

Time Complexity: O(2 ^ N)

Incall to ‘getResult()’, we are also calling the ‘helper’ function, and in the ‘helper’ function, we are checking all the valid options to make this two subsequences using a recursive call, therefore, the overall time complexity is O(2 ^ N).

Space Complexity: O(N)

As we are using ‘N’ extra space to store the binary tree, therefore, the overall space complexity will be O(N).

Check out this problem - 8 Queens Problem

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the subsequence?

subsequence is also a type of array which is contiguous and is usually a small section of the bigger array.

What is a boolean array?

The array in which the value of elements could be true or false only is a boolean array. 

Difference b/w recursion and backtracking?

Recursion and Backtracking are nearly similar because both call their own function again and again, but the only difference between both of them is that in recursion, the function calls stops when it satisfies the base case, whereas, in backtracking, recursion is used to check and find all possible combinations until and unless we get the best solution for that problem.

Conclusion

In this article, we discussed What Tug of war is, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Cheers!

Previous article
Word Break Problem using Backtracking
Next article
Permutations
Live masterclass