Predict the Winner

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
21 upvotes
Asked in companies
OlaSYSVINE

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
2
4
3
Sample Output 1:
3
1
Explanation of sample input 1:
For the first test case:
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 5 and leaves the game. Then the game resumes with person 5 having the ball in his hand. He passes the ball to person 1. The game pauses here. Person 1 passes the ball to person 3 and leaves the game. Then the game resumes with person 3 having the ball in his hand. He passes the ball to person 5. The game pauses here. Person 5 passes the ball to person 3 and leaves the game. Now only person 3 remains and the game stops here.

Hence, the winner of the game will be Person 3 and the answer will be 3.

For the second test case:
The game starts with Person 1. He passes the ball to person 2. Person 2 passes the ball to Person 3. The game pauses here. Person 3 passes the ball to Person 4 and leaves the game. Then the game resumes. Person 4 passes the ball to person 1. Person 1 passes the ball to person 2.The game pauses here. Person 2 passes the ball to person 4 and leaves the game. Then the game resumes with Person 4 having the ball in his hand. He passes the ball to person 1. Person 1 passes the ball to Person 4. The game pauses here. Person 4 passes the ball to person 1 and leaves the game. Now only person 1 remains and the game stops here.

Hence, the winner of the game will be Person 1 and the answer will be 1.
Sample Input 2:
1
4
1
Sample Output 2:
4
Hint

Try to simulate the game and find its winner.

Approaches (2)
Brute Force using Circular Linked List

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:

  1. Define a struct node having a pointer next and an integer shirtNo denoting shirt number.
  2. Initialize the head of the linked list with shirtNo=1.
  3. Initialize a pointer named curr currently pointing to head.
  4. Run a for loop for i from 2 to N, and do:
    1. For each, i Initialize a new node temp with shirtNo=i.
    2. Set curr -> next=temp
    3. Set curr = temp
  5. Make this linked list as circular linked list by doing curr->next=head
  6. Define a pointer ballInHand pointing to head and a currentPlayers integer variable to N.
  7. While currentPlayers is greater than 1:
    1. Do a for loop from i=1 to K-1 and set ballInHand to ballInHand-> next
    2. Set ballInHand->shirtNo to (ballInHand->next)->shirtNo
    3. Initialize a node temp as ballInHand->next
    4. set ballInHand->next as temp->next and delete the node to which temp is pointing.
    5. Decrease currentPlayers by 1.
  8. At last, return ballInHand->shirtNo as the winner of the game.
Time Complexity

O(N*K), where ‘N’ is the number of players of the game and 'K' is the jump parameter.

 

In the worst case, it takes K iterations to eliminate one person from the game and we need to eliminate N-1 persons from the game. Hence, the overall Time Complexity is O(N*K).

Space Complexity

O(N), where ‘N’ is the number of players of the game.

 

In the worst case, The number of elements in the circular linked list is N. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Predict the Winner
Full screen
Console