Tug Of War In C++

In this guide, we will explore the concept of Tug of war in C++ through illustrative instances.

One of the most well-known issues in computer science and mathematics is the tug of war . It is commonly referred to as the balance problem . In this task, we are taking a set of weights, and our objective is to split them into two groups as evenly as possible while minimizing the difference between the two groups' total weights. Follow the following steps to solve the tug of war problem:

• ✅ Divide a set of n integers into two subsets of size n/2 each, keeping the absolute difference between the two subsets as small as feasible. If n is odd, one subset's size must be (n-1)/2 and the second subset's size must be (n+1)/2 . If n is even, both subset sizes must be strictly n/2 .
• ✅ As an illustration, consider the following set: 3, 4, 5, -3, 100, 1, 89, 54, 23, 20. This set has a size of 10 . This set should provide the outputs 4, 100, 1, 23, 20, and 3, 5, -3, 89, 54. The sum of the elements in both of the output subsets, which are both of size 5, is the same (148 and 148).
• ✅ Consider yet another instance when n is odd. Give the set the following values: 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4. It is recommended that the output subsets be 45, -34, 12, 98, -1 and 23, 0, -99, 4, 189, 4. Elements in two subsets have sums of 120 and 121 .
• ✅ The next approach attempts each potential half-size subset. The remaining items make up the other subset if just one subset of half the size is generated. We start with an empty set and piece it together one by one. Each element can either be a part of the current set, or it can be a part of the remaining elements (another subset). We take into account both scenarios for every constituent. We determine whether this solution is superior to the best one up until the size of the current set reaches n/2 . If so, we revise the ideal solution.
• ✅ The solution to the problem of tug-of-war is given below. It outputs the necessary arrays.

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.
• ✅ In this tug-of-war issue, we must examine every feasible subsequence that is half as large as the input array, and then the leftover components will form the other subsequence. Using the boolean array , we will take into account where each element is located within its respective subsequence. If the current subsequence's size is half that of the input array during the procedure, we must determine whether the optimal solution is accessible or not.

Steps of Algorithm:

Create a function named "getResult" which accepts two arguments: a vector of integers named "input" and the size of this vector.

Initialize two boolean arrays named 'temp' and 'res', along with two integer variables 'mini' and 'sum', within the 'getResult' method as part of Step 2.

With the assistance of the variable 'i', proceed to iterate using the for loop to assign the total of all input elements to the variable 'sum', and set both boolean arrays 'temp' and 'res' to a value of 'false'.

Create a function named "helper" that accepts nine arguments: an array of integers named "input", the size of the array, a boolean array named "temp", the integer zero (representing the count of selected elements), another boolean array named "res", an integer variable named "mini", an integer variable named "sum", an integer variable named "currsum", and an integer variable named "curIndex + 1".

In this "helper" function, the "selected" variable is incremented, the value of the item at index "curIndex" in the "input" array is added to "cursum", and the element at index "cur_Index" in the "temp" array is set to "true".

Step 6: Verify if the selected value matches half of the vector's size. If this condition is met, the recommended approach is to check if the absolute difference between "sum / 2" and "curr_sum" is smaller than "mini". If this comparison holds true, update the "mini" value accordingly, and copy the entire temporary array to the "res" array using a for loop. If the condition is not satisfied, proceed to call the helper method iteratively while adjusting the parameters as specified in the code.

Set the 'cur_Index' of the temporary boolean array to 'false'.

Step 8: Print the entire sequence.

Program:

Let's consider an example to illustrate the competition between two forces 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 the 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 the 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 generates 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:

Complexity:

Time Complexity: O(2 ^ N)

When invoking the 'getResult' method, we also trigger the 'helper' function, which in turn examines all feasible choices to generate these two subsequences through recursive invocation. Consequently, the total time complexity amounts to O(2 ^ N).

Space Complexity: O(N)

Since 'N' additional space is required to store the binary tree, the total space complexity will amount to O(N).

Benefits of Tug of war in C++:

The "Two-Pointer Technique" or "Two-Sum Problem", often known as tug of war, is a frequent algorithmic technique used in computer science and programming, particularly in C++ and comparable programming languages. It is a method for effectively resolving particular kinds of problems, not a feature or library in C++. The following are some advantages of applying the Tug of War method in C++:

• ✅ Efficiency: When looking for matching pairs of items in an array or other data structures, the Tug of War technique is frequently employed to find solutions. With a temporal complexity of O(N) , where N is the size of the input data, it can often be quite effective.
• ✅ Optimization: When you need to identify the closest pair of items, two elements with a certain sum, or a way to divide an array into two subsets with the least amount of difference in their sums, this technique comes in extremely handy.
• ✅ Memory Efficiency: Tug of war is a memory-efficient method of problem-solving since it often employs a fixed amount of memory for variables and pointers.
• ✅ Simplicity: Simple implementation and application of the Tug of War technique in the C++ code are possible after we grasp its fundamental principles.
• ✅ Versatility: A wide range of issues, including those involving arrays, linked lists , and other data structures, can be addressed by using this technique. It is not constrained to a particular data or issue domain.
• ✅ Avoiding Nested Loops: Nested loops can be less effective and more difficult to manage in terms of code complexity; in some circumstances, employing Tug of War can assist you in avoiding using them.
• ✅ Reduced Time Complexity: Tug of War can be used to convert some problems from having an O(N2) (quadratic time) time complexity to having an O(N) (linear time) time complexity, greatly enhancing the effectiveness of your methods.

Conclusion:

While the Tug of War method offers several benefits, it's crucial to acknowledge that it may not be applicable in every scenario. Assess the specific problem at hand to determine the appropriateness of this method. Furthermore, honing skills and proficiency in algorithmic puzzle-solving might be essential to excel in implementing this tactic.