Equalize Weights

Moderate
0/80
Average time to solve is 15m
8 upvotes
Asked in company
IBM

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
3
3
9 1 4
2
5 6
3
2 11 7
Sample Output 1 :
1 5 9
2 6 7
4 11
Explanation For Sample Input 1 :
There are a total of three bags. After swapping 4 from the first bag and 5 from the second bag, the total sum of the first bag becomes equal to 15, and the total value of the second bag becomes 10. After swapping 6 from the second bag and 11 from the third bag, the total sum of the second bag becomes 15, and the sum of the third bag becomes 15, and thus, the total values of every bag become equal.
Since the least value is 1, we print the contents of the bag, which has the value 1 followed by the bag having the value 2, and finally the bag, which has the value 4.
Sample Input 2 :
1
2
3
4 1 2
2
5 6
Sample Output 2 :
2
1 2 6
4 5
Explanation For Sample Input 2 :
There are a total of two bags. After swapping 4 from the first bag and 6 from the second bag, the total sum of the first bag becomes equal to 9, and the total value of the second bag becomes 9, and thus, the total values of every bag become equal.
Since the least value is 1, we print the contents of the bag, which has the value 1, and finally the bag, which has the value 4.
Hint

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. 

Approaches (1)
Brute Force Approach

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 :

  1. Declare a variable, numOfBags to store the total number of bags.
  2. Create a vector, allItems to store the values of all the items.
  3. Create a vector, bagSizes to store the size of all the bags.
  4. Initialize a variable totalValue = 0.
  5. Run a loop from i=0 to i<numOfBags and do:
    1. Push bags[i].size() into bagSizes.
    2. For each value in bags[i], do :
      1. Add the value to the totalValue.
      2. Push the value into allItems.
  6. Declare a variable valuePerBag = totalValue / numOfBags.
  7. Define a vector of vector, equalBags to store the contents of the bags.
  8. Run a loop from i=0 to i=numOfBags and do:
    1. Declare a hashmap, checkItems.
    2. 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.
    3. Declare vectors remainingItems and currentBag.
    4. Run a loop from j=0 to j=allItems[j] and,
      1. If markedItems[j] is false, push it in remainingItems.
      2. Else, push it in currentBag.
    5. Make allItems = remainingItems.
    6. Push currentBag into equalBags.
  9. Run a loop from i=0 to i=numOfBags and sort equalBags[i].
  10. Sort equalBags to sort the contents of the bags in the required order.
  11. Return the vector, equalBags.

unordered_map<int, bool> currentBagItems(allItems, bagSize, valuePerBag, &checkItems, idx)

  1. If valueRemaining==0 and itemsRemaining==0, return checkItems.
  2. If valueRemaining<=0 or itemsRemaining<=0 or idx>=allItems.size(), return checkItems.
  3. Initialize ifNotTaken = currentBagItems(allItems, itemsRemaining , valueRemaining, checkItems, idx + 1 ).
  4. Make findItems = checkItems.
  5. Make findItems[ix] = true.
  6. Initialize ifTaken = currentBagItems(allItems, itemsRemaining-1 , valueRemaining-allItems[idx], findItems, idx + 1 ).
  7. If the size of ifTaken is more than 0, return ifTaken.
  8. Else, return ifNotTaken.
Time Complexity

O(2 ^ N), where N is the total number of items in all the bags.

 

The time complexity is O(2 ^ N) because for each bag size, out of all N values,  we are trying to find a subset containing these many values that can sum up to a certain value

Space Complexity

O(N), where N is the total number of items in all the bags.

 

We need extra linear space to maintain the hashmap that stores the contents for each bag.

Code Solution
(100% EXP penalty)
Equalize Weights
Full screen
Console