Josephus Problem in Linear Time and Constant Space
Follow the below steps to Solve the Problem (Approach):
- Initialize variables i and ans with 1 and 0 respectively.
- Run a while loop till i <= N:
- Update ans with (ans + k) % i.
- Increment i by 1.
- Return ans + 1 as the required answer.
Below is the Implementation of the above Steps:
// C++ code to Implement Josephus Problem
#include <iostream>
using namespace std;
int Josephus(int N, int k)
{
// Initialize variables i and ans with 1 and 0
// respectively.
int i = 1, ans = 0;
// Run a while loop till i <= N
while (i <= N) {
// Update the Value of ans and Increment i by 1
ans = (ans + k) % i;
i++;
}
// Return required answer
return ans + 1;
}
// main function
int main()
{
int N = 14, k = 2;
cout << Josephus(N, k) << endl;
return 0;
}
// This code is presented by Akash Mangal
// C Program to Implement Josephus Problem
#include <stdio.h>
int Josephus(int N, int k)
{
// Initialize variables i and ans with 1 and 0
// respectively.
int i = 1, ans = 0;
// Run a while loop till i <= N
while (i <= N) {
// Update the Value of ans and Increment i by 1
ans = (ans + k) % i;
i++;
}
// Return required answer
return ans + 1;
}
// main function
int main()
{
int N = 14, k = 2;
printf("%d", Josephus(N, k));
return 0;
}
// This code is presented by Akash Mangal
// Java code to Implement Josephus Problem
import java.io.*;
class GFG {
public static int Josephus(int N, int k) {
// Initialize variables i and ans with 1 and 0 respectively.
int i = 1, ans = 0;
// Run a while loop till i <= N
while (i <= N) {
// Update the Value of ans and Increment i by 1
ans = (ans + k) % i;
i++;
}
// Return required answer
return ans + 1;
}
// main function
public static void main (String[] args) {
int N = 14, k = 2;
int ans = Josephus(N, k);
System.out.println(ans);
}
}
// This code is presented by Akash Mangal
# python code to implement Josephus problem
# Josephus function which will take
# two parameter N and K, number of people and positions respectively
# return the position of person survives
def Josephus(n, k):
# initialize two variables i and ans
i = 1
ans = 0
while(i <= n):
# update the value of ans
ans = (ans + k) % i
i += 1
# returning the required answer
return ans + 1
# driver code
# let
n = 14
k = 2
result = Josephus(n, k)
print(result)
# This code is contributed by sarveshc111.
// C# code to Implement Josephus Problem
using System;
class GFG
{
public static int Josephus(int N, int k)
{
// Initialize variables i and ans with 1 and 0 respectively.
int i = 1, ans = 0;
// Run a while loop till i <= N
while (i <= N)
{
// Update the Value of ans and Increment i by 1
ans = (ans + k) % i;
i++;
}
// Return required answer
return ans + 1;
}
// main function
static void Main(string[] args)
{
int N = 14, k = 2;
int ans = Josephus(N, k);
Console.WriteLine(ans);
}
}
// driver code
let n = 14, k = 2;
document.write(Josephus(n,k));
// Josephus function
// return the position of last man survives
function Josephus(n, k)
{
let i = 1, ans = 0;
while(i <= n ){
// update the value of ans
ans = (ans + k) % i;
i++;
}
return ans + 1;
}
// This code is contributed by sarveshc111.
Output
13
Time Complexity: O(N)
Auxiliary Space: O(1)
Josephus Problem
There are N people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
Given the total number of persons N and a number k which indicates that k-1 persons are skipped and the kth person is killed in a circle. The task is to choose the person in the initial circle that survives.
Examples:
Input: N = 5 and k = 2
Output: 3
Explanation: Firstly, the person at position 2 is killed,
then the person at position 4 is killed, then the person at position 1 is killed.
Finally, the person at position 5 is killed. So the person at position 3 survives.Input: N = 7 and k = 3
Output: 4
Explanations: The persons at positions 3, 6, 2, 7, 5, and 1 are killed in order,
and the person at position 4 survives.