Josephus
‘N’ people are standing in a circle numbered from ‘1’ to ‘N’ in clockwise order. First, the person numbered 1 will proceed in a clockwise direction and will skip K-1 persons including itself and will kill a Kth person. Now (K+1)th person from 1 will start and will kill the Kth person from itself.

You have to find the position of the last person surviving with respect to initial numbering.

Note:

A person can also kill himself.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases. The first and only line of each test case contains two integers ‘N’ and ‘K’. Where ‘N’ is the total no of persons standing around circle and ‘K’ number indicates kth person is killed.

Output Format

For each test case, return a single integer denoting the position of the last person surviving.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints

1

Question

Josephus

‘N’ people are standing in a circle numbered from ‘1’ to ‘N’ in clockwise order. First, the person numbered 1 will proceed in a clockwise direction and will skip K-1 persons including itself and will kill a Kth person. Now (K+1)th person from 1 will start and will kill the Kth person from itself.

You have to find the position of the last person surviving with respect to initial numbering.

Note:

A person can also kill himself.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains two integers ‘N’ and ‘K’. Where ‘N’ is the total no of persons standing around circle and ‘K’  number indicates kth person is killed.

Output Format

For each test case, return a single integer denoting the position of the last person surviving.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints

1 <= ’T’ <= 50
1 <= ’N’,’K’ <= 10^4

Time Limit: 1 sec

Accepted Answer

This question is about finding the position of the last person surviving in a circle of N people, where each person kills the Kth person in a clockwise direction.

Implement a function that takes the number of test cases, N, and K as input
For each test case, simulate the killing process by iterating through the circle and skipping K-1 people
Keep track of the position of the last person surviving and return it as the output

Accepted Answer

Brute Force

Approach:- The key id is to store all positions of a person in vector and remove all kth position from starting point in vector. After removing an element from the vector starting point is also changed.

Algorithm:

Store all the positions of persons in the index array.
Initially the starting position will be 0(since pos[0]=1).
Delete the element at position 'START1'= (START + K - 1) % N. Whereas ‘N’ is the size of the index array.
Now the starting position will be ‘START1’.
Repeat step3 until size of array becomes equal to 1.
Return the only element of index array.

Space Complexity: O(n)Explanation:

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

Create an index array to store the positions of all persons.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of persons.

We iterate every index in worse case in each iteration we delete element from the array which takes O(N) time. Hence time complexity is O(N^2).

Python (3.5)

"""

    Time Complexity:O(N^2)

    Space Complexity:O(N)

   

    where 'N' is no of persons.

"""





def JosephusHelper(pos, si, k):

    while len(pos) > 1:



        # Index of element to be deleted.



        start = (si + k - 1) % len(pos)



        # Erasing the postion of person from list.



        del pos[start]



        # New position will be equal to.



        si = start



    return pos[0]





def Josephus(n, k):

    pos = []



    # Storing the positions of all persons.



    for i in range(1, n + 1):

        pos.append(i)



    return JosephusHelper(pos, 0, k)

Java (SE 1.8)

/*
   Time Complexity:O(N^2)
   Space Complexity:O(N)
   
   where 'N' is no of persons.
*/

import java.util.ArrayList;

public class Solution {
    public static int josephusHelper(ArrayList < Integer > pos, int si, int k) {
        while (pos.size() > 1) {
            // Index of element to be deleted.
            int start = (si + k - 1) % pos.size();
            // Erasing the postion of person from vector.
            pos.remove(start);
            // New position will be equal to.
            si = start;
        }

        // Returning the position of element to be deleted.
        return pos.get(0);
    }

    public static int josephus(int n, int k) {
        ArrayList < Integer > pos = new ArrayList < Integer > ();
        // Storing the positions of all persons.
        for (int i = 1; i <= n; i++) {
            pos.add(i);
        }

        return josephusHelper(pos, 0, k);
    }
}

C++ (g++ 5.4)

/*
   Time Complexity:O(N^2)
   Space Complexity:O(N)
   
   where 'N' is no of persons.
*/

int josephusHelper(vectorpos, int si, int k)
{
	while (pos.size() > 1)
	{	
		// Index of element to be deleted.
		int start = (si + k - 1) % pos.size();
		// Erasing the postion of person from vector.
		pos.erase(pos.begin() + start);
		// New position will be equal to.
		si = start;
	}

	// Returning the position of element to be deleted.
	return pos[0];
}

int josephus(int n, int k)
{
	vectorpos;
	// Storing the positions of all persons.
	for (int i = 1; i <= n; i++)
	{
		pos.push_back(i);
	}

	return josephusHelper(pos, 0, k);
}

Accepted Answer

Approach2

The key idea is find the answer for ‘N’ persons around the circle first find the answer for 'N-1' persons. First kill the Kth person from 1st position then recursively call on 'N-1'. It will give the position but according to with Kth person index set as 1. So to set the index will add ‘K’ to the index and will do mod ‘N’. If it comes out to be 0 then the value of index is ‘N’.

Algorithm:-

Consider the base case when ‘N’ == 1 so answer will be 1.
Recursively call on ‘N-1’ persons.It will give the position for ‘N-1’ persons .
The answer from recursion is position but according to the Kth person.So to covert, it into the original position add ‘K’ to it and do ‘N’ mod with it(If the value exceeds n so it has come back to starting positions). If it is equal to 0 then the index will be ‘N’.
Return the index

Space Complexity: O(1)Explanation:

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

As we are using recursive call ‘N-1’ times and each call will store in call stack which result in O(N).

Time Complexity: O(n)Explanation:

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

We call recursions ‘N-1’ times and do constant calculations. Hence time complexity is O(N)

Python (3.5)

"""

    Time Complexity:O(N)

    Space Complexity:O(N)



    where 'N' is no of persons.

"""



def Josephus(n, k):

    if (n == 1):

        return 1



        # Call recursion on n-1 persons and x contains answer for n-1 persons.

    x = Josephus(n - 1, k)

    # Setting x according to original position.

    x += (k)

    # If value of x exceeds n then it must again begin from starting indexes.

    x %= (n)

    # If x==0 it means that position is n.

    if (x == 0):

        x = n



    return x

C++ (g++ 5.4)

/*
   Time Complexity:O(N)
   Space Complexity:O(N)

   where 'N' is no of persons.
*/

int josephus(int n, int k)
{	
	//Base Case when n == 1.
	if (n == 1)
	{
		return 1;
	}

	// Call recursion on n-1 persons and x contains answer for n-1 persons.
	int x = josephus(n - 1, k);
	// Setting x according to original position.
	x += (k);
	// If value of x exceeds n then it must again begin from starting indexes.
	x %= (n);
	// If x==0 it means that position is n.
	if (x == 0)
	{
		x = n;
	}

	return x;
}

Java (SE 1.8)

/*
   Time Complexity:O(N)
   Space Complexity:O(N)

   where 'N' is no of persons.
*/

public class Solution {
    
    public static int josephus(int n, int k) {
        //Base Case when n == 1.
		if (n == 1)
		{
			return 1;
		}

		// Call recursion on n-1 persons and x contains answer for n-1 persons.
		int x = josephus(n - 1, k);
		// Setting x according to original position.
		x += (k);
		// If value of x exceeds n then it must again begin from starting indexes.
		x %= (n);
		// If x==0 it means that position is n.
		if (x == 0)
		{
			x = n;
		}
		
		return x; 
    }
}

You have to find the position of the last person surviving with respect to initial numbering.

Note:

Input Format

Output Format

Note:

Constraints

Top Texas Instruments Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern