Approach to solve Josephus problem iteratively
Illustration:
N = 5, k = 2
Add all values from 1 to N in the list. We will call the recursive function with start = 0 and k = 1 (0-indexing)
Now the element at 1-index (person number 2) will be killed. And it is removed from the list. The new counting will begin from 1-index, the person at 1-index killed so now person at 2-index (person number 3) comes to 1-index and counting starts from here now.
Now we have 4 people, counting starting from 1-index (person number 3) and the person at kth (2-index ) position will be killed.
The person at 2-index (person number 4) was killed so now we have 3 people left and the person (person number 5) at 3-index shifted to 2-index. And counting starts from here.
The person at the 0-index was killed and we have now two-person left in the circle. And the person at 1-index shifted to 0-index i.e. person number 3.
Final counting done and the person at 1-index killed and the only person who is left is at position 3.
Follow the below steps to Implement the idea:
- Initialize variables num, cnt, and cut with 1, 0, and 0 respectively and an array arr[] of size N with the initial value set as 1.
- Run a while loop till cnt < N:
- Run a while loop till num is less than equal to k.
- Increment cut by one and take modulo by N
- If arr[cut] = 1 increment num by one.
- Set num = 1, arr[cut] = 0 and increment cnt and cut by one and cut = cut % n;
- Run a while loop till arr[cut] = 0 and increment cut by one.
- Run a while loop till num is less than equal to k.
- Return cnt + 1 as the required answer.
Below is the Implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
int Josephus(int, int);
int Josephus(int n, int k)
{
k--;
int arr[n];
// Makes all the 'n' people alive by
// assigning them value = 1
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
int cnt = 0, cut = 0,
// Cut = 0 gives the sword to 1st person.
num = 1;
// Loop continues till n-1 person dies.
while (cnt < (n - 1)) {
// Checks next (kth) alive persons.
while (num <= k) {
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
if (arr[cut] == 1) {
// Updates the number of persons
// alive.
num++;
}
}
// Refreshes value to 1 for next use.
num = 1;
// Kills the person at position of 'cut'
arr[cut] = 0;
// Updates the no. of killed persons.
cnt++;
cut++;
// Checks and resolves overflow of Index.
cut = cut % n;
// Checks the next alive person the
// sword is to be given.
while (arr[cut] == 0) {
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
}
}
// Output is the position of the last
// man alive(Index + 1);
return cut + 1;
}
// Driver code
int main()
{
int n = 14, k = 2;
cout << Josephus(n, k);
return 0;
}
// THIS CODE IS PRESENTED BY SHISHANK RAWAT
// Java code to implement the above approach
import java.io.*;
class GFG {
public static void main(String[] args)
{
int n = 14, k = 2;
System.out.println(Josephus(n, k));
}
public static int Josephus(int n, int k)
{
k--;
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1; // Makes all the 'n' people alive by
// assigning them value = 1
}
int cnt = 0, cut = 0,
num
= 1; // Cut = 0 gives the sword to 1st person.
while (
cnt
< (n
- 1)) // Loop continues till n-1 person dies.
{
while (num
<= k) // Checks next (kth) alive persons.
{
cut++;
cut = cut
% n; // Checks and resolves overflow
// of Index.
if (arr[cut] == 1) {
num++; // Updates the number of persons
// alive.
}
}
num = 1; // refreshes value to 1 for next use.
arr[cut] = 0; // Kills the person at position of
// 'cut'
cnt++; // Updates the no. of killed persons.
cut++;
cut = cut % n; // Checks and resolves overflow
// of Index.
while (arr[cut]
== 0) // Checks the next alive person the
// sword is to be given.
{
cut++;
cut = cut
% n; // Checks and resolves overflow
// of Index.
}
}
return cut
+ 1; // Output is the position of the last
// man alive(Index + 1);
}
}
// This code is contributed by Shubham Singh
def Josephus(n, k):
k -= 1
arr = [0]*n
for i in range(n):
arr[i] = 1 # Makes all the 'n' people alive by
# assigning them value = 1
cnt = 0
cut = 0
num = 1 # Cut = 0 gives the sword to 1st person.
while (cnt < (n - 1)):
# Loop continues till n-1 person dies.
while (num <= k):
# Checks next (kth) alive persons.
cut += 1
cut = cut % n # Checks and resolves overflow
# of Index.
if (arr[cut] == 1):
num+=1 # Updates the number of persons
# alive.
num = 1 # refreshes value to 1 for next use.
arr[cut] = 0 # Kills the person at position of 'cut'
cnt += 1 # Updates the no. of killed persons.
cut += 1
cut = cut % n # Checks and resolves overflow of Index.
while (arr[cut] == 0):
# Checks the next alive person the
# sword is to be given.
cut += 1
cut = cut % n # Checks and resolves overflow
# of Index.
return cut + 1 # Output is the position of the last
# man alive(Index + 1)
# Driver Code
n, k = 14, 2 #map (int, input().splut())
print(Josephus(n, k))
# This code is contributed by ShubhamSingh
// C# code to implement the above approach
using System;
using System.Linq;
public class GFG{
public static void Main ()
{
int n = 14, k = 2;
Console.Write(Josephus(n, k));
}
public static int Josephus(int n, int k)
{
k--;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1; // Makes all the 'n' people alive by
// assigning them value = 1
}
int cnt = 0, cut = 0,
num = 1; // Cut = 0 gives the sword to 1st person.
while (
cnt
< (n - 1)) // Loop continues till n-1 person dies.
{
while (num <= k) // Checks next (kth) alive persons.
{
cut++;
cut = cut % n;
// Checks and resolves overflow
// of Index.
if (arr[cut] == 1)
{
num++; // Updates the number of persons
// alive.
}
}
num = 1; // refreshes value to 1 for next use.
arr[cut]
= 0; // Kills the person at position of 'cut'
cnt++; // Updates the no. of killed persons.
cut++;
cut = cut
% n; // Checks and resolves overflow of Index.
while (arr[cut]
== 0) // Checks the next alive person the
// sword is to be given.
{
cut++;
cut = cut % n; // Checks and resolves overflow
// of Index.
}
}
return cut + 1; // Output is the position of the last
// man alive(Index + 1);
}
}
// This code is contributed by Shubham Singh
<script>
// Javascript code to implement the above approach
let n = 14, k = 2;
document.write(Josephus(n, k));
function Josephus(n, k)
{
k--;
let arr = new Array(n);
for (let i = 0; i < n; i++)
{
// Makes all the 'n' people alive by
// assigning them value = 1
arr[i] = 1;
}
// Cut = 0 gives the sword to 1st person.
let cnt = 0, cut = 0,
num = 1;
// Loop continues till n-1 person dies.
while (cnt < (n - 1))
{
// Checks next (kth) alive persons.
while (num <= k)
{
cut++;
cut = cut % n;
// Checks and resolves overflow
// of Index.
if (arr[cut] == 1)
{
// Updates the number of persons
// alive.
num++;
}
}
// refreshes value to 1 for next use.
num = 1;
arr[cut] = 0; // Kills the person at position of 'cut'
// Updates the no. of killed persons.
cnt++;
cut++;
// Checks and resolves overflow of Index.
cut = cut % n;
// Checks the next alive person the
// sword is to be given.
while (arr[cut] == 0)
{
cut++;
// Checks and resolves overflow
// of Index.
cut = cut % n;
}
}
// Output is the position of the last
// man alive(Index + 1);
return cut + 1;
}
// This code is contributed by decode2207.
</script>
Output
13
Time Complexity: O(N2)
Auxiliary Space: O(N)
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.