Last Updated: 7 Jan, 2021
Predict the Winner
Moderate
Asked in companies
There are 'N' persons standing in a circular queue. There is a number written on the back of the shirts of every person. One person among them has a ball in his hands and the number written on his shirt's back is 1. The number written on the shirt of every other person is 1 more than the number written on the shirt of the person standing to the left of him. We have also been provided with an integer 'K' denoting the jump parameter. They start playing a game. The game proceeds as follows:
1. If there is only one person remaining in the game then the game stops immediately and the person is declared the winner.
2. The player who currently has the ball in its hand passes the ball to the person standing to his right.
3. Step 2 happens exactly 'K'-1 times.
4. The game pauses here and the person who has the ball in his hand currently has to pass the ball to the person standing on his right and has to leave the game.
5. Again the game resumes with the remaining players.
You have been provided with positive integers 'N' and 'K'. Your task is to find the number written on the back of the winner when the game is played with 'N' members using the jump parameter 'K'.
For example:
N=4, K=2 -> K-1=1
The game starts with Person 1. He passes the ball to person 2. The game pauses here. Person 2 passes the ball to person 3 and leaves the game. Then the game resumes. Person 3 passes the ball to person 4. The game pauses here. Person 4 passes the ball to person 1 and leaves the game. Then the game resumes with person 1 having the ball in his hand. He passes the ball to person 3. The game pauses here. Person 3 passes the ball to person 1 and leaves the game. Now only person 1 remains and the game stops here.
Note
You are not required to print anything, just implement the given function and return the number written on the shirt of the winner of the game.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’ denoting the number of players in the game.
The second line of each test case contains an integer ‘K' denoting the jump parameter in the game.
Output Format
For each test case, print the number written on the back of the winner when the game is played with 'N' members using the jump parameter 'K'.
Print the output of each test case in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= K <= 10 ^ 9
Time limit: 1 second
Approaches
The idea is to simulate the game as mentioned and find the winner of the game. The main objective is to decide the data structure to use. We need to use a data structure which is circular and elements from it can be deleted anywhere. Therefore, we will be using a circular singly linked list to simulate the process as it is circular in nature and we can delete a node from it anywhere in constant time.
First of all, we create a circular linked list of length N with values of nodes assigned 1,2….N respectively. Then we will start simulating the game until the length of the linked list is greater than 1. To simulate one iteration of the game we first initialize an iterator at the head of the linked list and move that iterator K-1 times to the right. Delete the node currently at that position. Move the iterator to the right and restart the game.
Steps:
- Define a struct node having a pointer next and an integer shirtNo denoting shirt number.
- Initialize the head of the linked list with shirtNo=1.
- Initialize a pointer named curr currently pointing to head.
- Run a for loop for i from 2 to N, and do:
- For each, i Initialize a new node temp with shirtNo=i.
- Set curr -> next=temp
- Set curr = temp
- Make this linked list as circular linked list by doing curr->next=head
- Define a pointer ballInHand pointing to head and a currentPlayers integer variable to N.
- While currentPlayers is greater than 1:
- Do a for loop from i=1 to K-1 and set ballInHand to ballInHand-> next
- Set ballInHand->shirtNo to (ballInHand->next)->shirtNo
- Initialize a node temp as ballInHand->next
- set ballInHand->next as temp->next and delete the node to which temp is pointing.
- Decrease currentPlayers by 1.
- At last, return ballInHand->shirtNo as the winner of the game.
The idea is to first think of a recursive relation to predict the winner of the game and then optimize the recursive approach to an iterative approach to solve the problem in an optimal manner as also explained in this article.
Let predictTheWinner(N,K) denotes the winner of the game when it is played with N players using the jump parameter K.
We can find the winner of the game using the recursive relation
predictTheWinner(N, K) = predictTheWinner((N - 1, K) + K-1) % N + 1 with the base case predictTheWinner(1, K) = 1.
We can think of the recursive relation as:
When the first person (Kth from starting) is eliminated, N-1 persons are left. So we call predictTheWinner(N - 1, K) to find the winner when N-1 players are playing. But the shirtNo returned by predictTheWinner(N - 1, K) will treat the player with shirtNo K%M + 1 as the first player. So, we need to make changes to the shirtNo returned by predictTheWinner(N - 1, K).
Now we will convert the recursive solution in iteration one.
Steps:
- Initialize a variable winnerOfTheGame with value 0
- Run a for loop for i=1 to N and in each iteration
- Set winnerOfTheGame as (winnerOfTheGame+K)%i
- At last return winnerOfTheGame+1 as the final winner of the game