question archive A group of children want to play a game where in each turn the player with the most money must give half of his/her money to the player with the least amount of money
A group of children want to play a game where in each turn the player with the most money must give half of his/her money to the player with the least amount of money
Subject:Computer SciencePrice:2.87 Bought7
A group of children want to play a game where in each turn the player with the most money must give half of his/her money to the player with the least amount of money. If there is a tie in terms of the wealthiest or poorest player, one is selected at random.
What data structure(s) should be used to play this game efficiently?
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
Answer:
If we will use max heap, then the root will be the children with highest amount of money and just give half of his money to the children having least money and then call "Max-Heapify".
Thus space complexity: O(N)
Time Complexity: O(N + NlogN)
