N people stand in a circle and every k-th person is eliminated until one remains. Simulate it with an ArrayDeque (rotate by polling and offering) for N = 7, k = 3.
Solution
Main.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Main {
static int josephus(int n, int k, List<Integer> order) {
Deque<Integer> circle = new ArrayDeque<>();
for (int i = 1; i <= n; i++) circle.offer(i);
while (circle.size() > 1) {
for (int i = 1; i < k; i++) circle.offer(circle.poll()); // move k-1 people to the back
order.add(circle.poll()); // the k-th is out
}
return circle.peek();
}
public static void main(String[] args) {
List<Integer> out = new ArrayList<>();
int survivor = josephus(7, 3, out);
System.out.println("eliminated " + out + ", survivor " + survivor);
System.out.println("n=10 k=2 survivor " + josephus(10, 2, new ArrayList<>()));
}
}
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!