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

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 + 1
N = 5
k = 2
result = find_last_survivor(N, k)
print("Position of the last survivor:", result) # Output: 3

Asked by: Bloomberg