ou are playing a game with the following strange rules as follows:
There are n rooms full of identical boxes randomly distributed among these rooms. Your
game consists of two steps:
1. Chooses an arbitrary room, let's say room number i, only once.
2. Move all boxes from such source room (chosen in step 1) and distribute them on
the other rooms as you like.
Winning/Losing Condition: If you can distribute the boxes taken from room i on the
other remaining n-1 rooms in a way that makes all the remaining rooms having the same
number of boxes, then you win the game, otherwise, otherwise you will lose.
In order to win this strange game, I allow you to put several extra boxes into any of the
existing rooms in such a way that no matter which room i you choose, you will win. What
is the minimum number of extra boxes you need to put?
Examples:
Input Output Explanation
Test
case 1:
[ 3, 2, 2]
(i.e., there are three
rooms, where the first
room has 3 boxes,
second room has 2
boxes, and third room
has 2 boxes
1 You can put minimum one extra box into the
first room and make a = [4,2,2]. This will
enable you to play the game and win as
follows: If you choose the room one
with 4 boxes, then we will move two boxes to
the second room and two boxes to the third
room. If you choose the second or third room,
with 2 boxes then you will move these two
boxes to the other room with 2 blocks.
Test
case 2:
[6,4,4,4] 0 In the second test case, you don't need to put
any extra box, since no matter which room
you choose, you can always make other
rooms equal.
Test
case 3:
[5,0,0,] 5 In the third test case, you should
put minimum 5 extra boxes. For example,
you can put 3 boxes in the second room and 2
boxes in the third room. You'll get an array of
[5,3,2]. In this way, no matter the room
you will choose, you can always win.
a) Design an algorithm to solve this problem with the least possible complexity (10
marks),
b) Analyse the complexity of your solution. (4 marks)
c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks
depend on the correctness of the code, indentation, comments, test-case]
d) Prepare a brief report (250 words) comparing your algorithm with the brute force
approach (6 marks)