Last Updated: 16 Mar, 2021
Equalize Weights
Moderate
Asked in company
You are given an integer ‘N’, denoting the total number of bags. Each bag contains some items, and each item has a value attached to it. Your task is to equalize the total value of all the bags by swapping any two items, and the following rules must be followed :
The number of items in a bag must remain constant before and after swapping.
Any number of swappings is permitted.
It is guaranteed that there is at least one way to make the values of all the bags equal to each other.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases or queries to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains an integer ‘N’, denoting the total number of bags. The next 2*’N’ lines contain the following :
The first line contains a single integer ‘M’, denoting the number of items in the bag.
The second line contains ‘M’ space-separated integers, denoting the value of each item in the bag.
Output Format :
For each test case, print in a new line the contents of every bag in non-decreasing order.
Output for each test case will be printed in a separate line.
The contents of all the bags must be printed in separate lines, and the following rules must be followed :
The contents of the bag that contains the item having the least value must be printed on the first line.
The contents of the bag that contains the item having the second least value must be printed on the second line and so on and so forth.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N,M <= 10
1 <= X <= 10^4
Where 'X' is the value of any item in any bag
Time Limit: 1sec
Approaches
Approach:
The approach is to find out the required value for each bag. We need to store the sizes of all the bags and the values of all the items. Then for each size, we can find out these many values that can sum up to the required weight for each bag. We can keep doing this for all bags and finally when we get our result, we can simply sort the contents in the required order and return the values.
Steps :
- Declare a variable, numOfBags to store the total number of bags.
- Create a vector, allItems to store the values of all the items.
- Create a vector, bagSizes to store the size of all the bags.
- Initialize a variable totalValue = 0.
- Run a loop from i=0 to i<numOfBags and do:
- Push bags[i].size() into bagSizes.
- For each value in bags[i], do :
- Add the value to the totalValue.
- Push the value into allItems.
- Declare a variable valuePerBag = totalValue / numOfBags.
- Define a vector of vector, equalBags to store the contents of the bags.
- Run a loop from i=0 to i=numOfBags and do:
- Declare a hashmap, checkItems.
- Declare a hashmap markedItemsto store the result of currentBagItems(allItems, bagSizes[i], valuePerBag, checkItems, 0). This function will mark all the chosen items for the current bag as true.
- Declare vectors remainingItems and currentBag.
- Run a loop from j=0 to j=allItems[j] and,
- If markedItems[j] is false, push it in remainingItems.
- Else, push it in currentBag.
- Make allItems = remainingItems.
- Push currentBag into equalBags.
- Run a loop from i=0 to i=numOfBags and sort equalBags[i].
- Sort equalBags to sort the contents of the bags in the required order.
- Return the vector, equalBags.
unordered_map<int, bool> currentBagItems(allItems, bagSize, valuePerBag, &checkItems, idx)
- If valueRemaining==0 and itemsRemaining==0, return checkItems.
- If valueRemaining<=0 or itemsRemaining<=0 or idx>=allItems.size(), return checkItems.
- Initialize ifNotTaken = currentBagItems(allItems, itemsRemaining , valueRemaining, checkItems, idx + 1 ).
- Make findItems = checkItems.
- Make findItems[ix] = true.
- Initialize ifTaken = currentBagItems(allItems, itemsRemaining-1 , valueRemaining-allItems[idx], findItems, idx + 1 ).
- If the size of ifTaken is more than 0, return ifTaken.
- Else, return ifNotTaken.