LearnFrenzy
Sign in Take a free test

Collections Framework · Collections Programs · Question 9

Josephus elimination game with a queue in Java Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 9 Back to Exercise

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<>()));
    }
}

Output Verified by compiling and running

eliminated [3, 6, 2, 7, 5, 1], survivor 4
n=10 k=2 survivor 5

Rotating a queue models walking round the circle; each poll at the k-th step removes one person.

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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links