# Problem: There are N prisoners standing in a circle, waiting to be executed…

By | June 27, 2023

There are N prisoners standing in a circle, waiting to be executed. The executions are carried out starting with the kth person, and removing every successive kth person going clockwise until there is no one left. Given N and k, write an algorithm to determine where a prisoner should stand in order to be the last survivor. For example, if N = 5 and k = 2, the order of executions would be [2, 4, 1, 5, 3], so you should return 3.

Java

`public class LastSurvivor {    public static int findLastSurvivor(int N, int k) {        int lastSurvivor = 0;        for (int i = 2; i <= N; i++) {            lastSurvivor = (lastSurvivor + k) % i;        }        return lastSurvivor + 1;    }    public static void main(String[] args) {        int N = 5;        int k = 2;        int result = findLastSurvivor(N, k);        System.out.println("Position of the last survivor: " + result); // Output: 3    }}`

Javascript

`function findLastSurvivor(N, k) {    let lastSurvivor = 0;    for (let i = 2; i <= N; i++) {        lastSurvivor = (lastSurvivor + k) % i;    }    return lastSurvivor + 1;}const N = 5;const k = 2;const result = findLastSurvivor(N, k);console.log("Position of the last survivor: " + result); // Output: 3`

Python

`def find_last_survivor(N, k):    last_survivor = 0    for i in range(2, N + 1):        last_survivor = (last_survivor + k) % i    return last_survivor + 1N = 5k = 2result = find_last_survivor(N, k)print("Position of the last survivor:", result) # Output: 3`