In the childrens game hot potato, a group of n children sit in a circle passing an
Question:
In the children’s game “hot potato,” a group of n children sit in a circle passing an object, called the “potato,” around the circle (say in a clockwise direction). The children continue passing the potato until a leader rings a bell, at which point the child holding the potato must leave the game, and the other children close up the circle. This process is then continued until there is only one child remaining, who is declared the winner. Using a list, describe an efficient method for implementing this game. Suppose the leader always rings the bell immediately after the potato has been passed k times. (Determining the last child remaining in this variation of hot potato is known as the Josephus problem.)
What is the running time of your method in terms of n and k, assuming the list is implemented with a doubly linked list? What if the list is implemented with an array?
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia