Tug of War

Easy
0/40
Average time to solve is 15m
40 upvotes
Asked in company
Barclays

Problem statement

You are a coach of a group consisting of 'N' students. The ith student has a strength Arr[i]. For a Tug of War game, you want to divide students into two teams of equal size (If N is odd, then size of one team should be (N-1)/2 and size of other team should be (N+1)/2). You want a game that is fun, for this the absolute difference between the team’s strength should be as minimum as possible. A team's strength is the sum of the strengths of the students in the team.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 

Then the 'T' test cases follow.

The first line of each test case contains a positive integer 'N', which represents the number of students.

The next line contains 'N' single space-separated integers representing the strength of the students.
Output Format : 
For each test case, print the minimum absolute difference between the team’s strength.

The output of each test case is printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
2 <= N <= 20
0 < Arr[i] <= 10^5
Where T is the number of test cases, N is the number of students and Arr[i] is the strength of ith student.
Sample Input 1:
3
4
1 2 3 4
3
4 2 1
2
6 8
Sample Output 1:
0
1
2
Explanation for Sample Input 1:
In the 1st test case, the first team contains students with strength {1, 4} and the second team contains students with strength {2, 3}, the absolute difference between the team’s strength is (1+5)-(2+3)=0.

In the 2nd test case, the first team contains students with strength {1, 2} and the second team contains students with strength {4}, the absolute difference between the team’s strength is (4)-(1+2)=1.

In the 3rd test case, the first team contains students with strength {6} and the second team contains students with strength {8}, the absolute difference between the team’s strength is (8)-(6)=2.
Sample Input 2:
2
3
10 10 10
4
10 1 2 5
Sample Output 2:
10
4
Hint

Check every possible subset of size N/2.

Approaches (1)
Recursive Approach

The idea is to find all possible subsets of size N/2.

Let’s say we have a subset of size N/2, ‘subsetSum’ will be the sum of strength of this subset and ‘totalSum’ will be the sum of strength of all N students. Then, the absolute difference between the team’s strength will be | (totalSum - subsetSum) - subsetSum |, which is equal to | totalSum - 2 * subsetSum |.
 

We will use recursion to find the subset.
 

Algorithm:

Let’s define a function tugOfWarHelper(i, subsetSum, cnt, totalSum), where i is the current index, subsetSum is sum of strength in the subset and cnt is the number of students in the subset. This function returns the minimum absolute difference.

Each student has two choices: either it will be included in the current subset or not.
 

Base Case: 

If i is equal to N:

  • If cnt is equal to N/2, return absolute difference,i.e, | totalSum -2* subsetSum |.
  • Else, return an infinite value (INT_MAX)
     

Recursive States:

Return minimum of :

  • tugOfWarHelper(i + 1, subsetSum, cnt, totalSum)
  • tugOfWarHelper(i + 1, subsetSum + Arr[i], cnt + 1, totalSum)
Time Complexity

O(2 ^ N), Where N is the number of students.
 

Every student has two choices, to be in either of the teams, so there will be 2 ^ N possible subsets. Thus, the final time complexity is O(2 ^ N)

Space Complexity

O(N), Where N is the number of students.
 

O(N) recursion stack space is used by the recursive function. Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Tug of War
Full screen
Console