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