Last Updated: 15 Mar, 2021
Split Array With the Same Average
Hard
Asked in companies
A group of ninjas want to play a game of tag but they can only do that if each team has the same average strength of abilities among the two divided teams. You are given a list (array named ‘strengths’) of the strengths of the group of ninjas represented by numbers (integers). You have to determine whether those ninjas can be regrouped into two different teams such that the average strength of the two teams formed is equal.
Note:
You have to move each ninja of given strength from the given list into two separate teams (list) ‘Team_A’ and ‘Team_B’ such that the average strengths of ‘Team_A’ == ‘Team_B’. There has to be at least one member in each team since they cannot play the game without that.
For Example:
Input : [1, 7, 15, 29, 11, 9]
Output : [9, 15] [1, 7, 11, 29]
Explanation: The average strengths of both the teams is 12
Input Format:
The first line of input contains a single integer ‘N’ denoting the number of ninjas, whose list of strengths which would be given in the list.
The second line contains ‘N’ single space-separated integers, denoting the strengths of the ninjas.
Output Format :
Print "True" if the ninjas can be regrouped into two different teams having same average strengths and "False" is they cannot be regrouped.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= N <= 30
0 <= strengths[i] <= 10^4
Time Limit: 1 sec
Approaches
The idea here is that for each element you have 2 options (like in a Knapsack problem), select the ninja member in B or A. The sum of strengths of ninjas in team B is the sum of numbers in B and n is the number of elements in B. The states can’t be uniquely classified by just ‘i’ and sum because you can obtain the same sum value by selecting a different number of elements, which will affect the average.
Assume we split the total ninjas (let list (array) ‘strengths’ denote the list of strengths of the total ninjas given to us) into ‘A’ and ‘B’ so that avg(A) == avg(B).
Notice a fact that in this problem we have: avg(strengths) == avg(A) == avg(B)
So we only need to find a proper subset B such that avg(B) == avg(strengths) and we can just put the remaining elements in A.
Now if avg(B)==avg(strengths), that means sum(B) / B.length == sum(strengths) / N
or, sum(B) == sum(strenghts) * B.length / N
That means we need to find a subset B, such that its sum and length satisfies this condition.
The algorithm will be:
- We will initialise a dictionary ‘DP’ (for faster lookups) which would have the values of whether the selected subsets would result into a sum that we require.
- We will use a subfunction that checks if the total ‘K’ elements sums to a ‘TARGET’ value in each iteration. Here, ‘TARGET’ is the goal, ‘K’ is the number of elements in set ‘B’, while ‘i’ is the index we have traversed through so far.
- Inititalise ‘N’ with the total length of the strengths of ninjas given and ‘S’ with the sum of total strengths given in the list.
- Now for we iterate for each possible length ‘j’ of subset ‘B’ from length 1 to length ‘N’ // 2 + 1 and we check if we can find targetSum ‘S’ * ‘j’ // ‘N’ (total sum of j elements that sums to s*j//n) for each function call (named: ‘FIND’) we will check:
- If we are down searching for ‘K’ elements in the array, see if the ‘TARGETSUM’ is 0 or not, which would be the basecase.
- If the to-be selected elements in ‘B[K]’ + elements we have traversed so far is larger than total length of A, even if we choose all elements, we don't have enough elements left, there should be no valid answer.
- If there is already a calculated value for the (TARGET, K, i) in the ‘DP’ dictionary we directly return that as DP[(TARGET, K, i)]
- Otherwise, we calculate the ith element by:
- DP[(TARGETSUM - STRENGTHS[i], K - 1, i + 1)] = find(TARGETSUM - STRENGTHS[i], k-1, i + 1) or find(TARGETSUM, K, i + 1)
- Atlast we will return True if any of those subsets are found in the function otherwise we return False.
Similar problems