Find the Winner of the Circular Game Solution using Recursion | Josephus Problem

Find the Winner of the Circular Game Solution using Recursion with Explanation

 

Problem Description :

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1. Start at the 1st friend.
2. Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
3. The last friend you counted leaves the circle and loses the game.
4. If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
5. Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

This problem is also called Josephus Problem. To learn more about this problem

• Josephus problem
  

Example 1 :

Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2 :

Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.
 

So, we have to delete k value until only one element remaining in list.

Here we can use many Data structure like, ArrayList, LinkedList, Queue, etc..

In solution 1, we will use ArrayList data structure for storing n values and use Recursion approach for solving problem.

Solution 1 :

class Solution {

    public int findTheWinner(int n, int k) {
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i+1);
        }
       
        // Pass list, starting from 0, next k location for remove
        // List index start from 0, so We are starting from 0 and passing k-1
        return removeElements(list, 0, k-1);
    }
    
    private static int removeElements(List<Integer> list, int start, int k) {
       
        if (list.size() == 1) {
            return list.get(0);
        }
       
        start = (start+k) % list.size();
        list.remove(start);
        return removeElements(list, start, k);
    }
}

Solution Explanation :

n = 5, k = 2

• In findTheWinner() method, create array list and initialize with 1 to n values. 
• Call removeElements() method with list, start, and k parameters.
  

list = [1, 2, 3, 4, 5], n = 5, k = 1, start = 0

• removeElements([1, 2, 3, 4, 5], 0, 1)
  
• list.size() == 1 | 5 == 1 becomes false
• start = (0+1) % 5 = 1
• list.remove(1) | remove element from index 1, remove 2 from list
  
• removeElements([1, 3, 4, 5], 1, 1)
• 4 == 1 becomes false
• start = (1+1) % 4 = 2
• list.remove(2) | remove element from index 2, remove 4 from list
• removeElements([1, 3, 5], 2, 1)
• 3 == 1 becomes false
• start = (2+1) % 3 = 0
• list.remove(0) | remove element from index 0, remove 1 from list
• removeElements([3, 5], 0, 1)
• 2 == 1 becomes false
• start = (0+1) % 2 =1
• list.remove(1) | remove element from index 1, remove 5 from list
• removeElements([3], 1, 1)
• 1 == 1 becomes true
  
• return list.get(0) | return 3

If you have any query on above solution, you can freely contact me or comment down.

Happy coding...

RECOMMENDED ARTICLES :

• Check Palindrome Linked List using Recursive and Two Pointer Approach in Java with Explanation 
• find Given Number is Power of Two or Not in Java and Python