Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Josephus Problem

Problem Statement

Write a Java program to solve the Josephus problem using a circular linked list. The Josephus problem involves n people standing in a circle, numbered from 1 to n, where every k-th person is eliminated until only one remains. The circular linked list is a singly linked list where the last node’s next pointer points to the head, forming a cycle. The program should return the value of the last person remaining and test the solution with different values of k and list sizes, including edge cases like single-person lists and k=1. You can visualize this as a circle of numbered cards where every k-th card is removed until only one card remains.

Input:

  • A circular linked list of integers representing people (e.g., 1→2→3→4→1 for n=4) and an integer k (the step size for elimination). Output: The value of the last person remaining (e.g., 3 for n=4, k=2). Constraints:
  • The list size n is between 1 and 10^5.
  • Node values are integers from 1 to n.
  • k is a positive integer (k ≥ 1). Example:
  • Input: List = 1→2→3→4→1, k = 2
  • Output: 3
  • Explanation: Eliminate every 2nd person: 2, 4, 1, leaving 3.
  • Input: List = 1→1, k = 1
  • Output: 1
  • Explanation: Single person remains.
  • Input: List = 1→2→3→1, k = 3
  • Output: 1
  • Explanation: Eliminate every 3rd person: 3, 2, leaving 1.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION solveJosephus(head, k)
    IF head is null THEN
        RETURN -1
    ENDIF
    IF head.next is head THEN
        RETURN head.value
    ENDIF
    SET current to head
    WHILE current.next is not current
        FOR i from 1 to k-1
            SET current to current.next
        ENDFOR
        SET nextNode to current.next
        SET current.next to nextNode.next
        SET current to current.next
    ENDWHILE
    RETURN current.value
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    SET visited as new Set
    WHILE current is not null AND current not in visited
        ADD current to visited
        APPEND current.value to result
        IF current.next is not head THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of test cases (list values, k)
    FOR each testCase in testCases
        PRINT test case details
        CALL solveJosephus(testCase.head, testCase.k)
        PRINT last person remaining
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a Node class with: a. An integer value (person number). b. A next pointer to the next node.
  2. In solveJosephus: a. If the list is empty, return -1. b. If the list has one node, return its value. c. Set current to head. d. While more than one node remains:
    • Traverse k-1 steps to find the node before the one to eliminate.
    • Remove the k-th node by updating current.next to skip it.
    • Move current to the next node. e. Return the value of the last remaining node.
  3. In toString: a. If head is null, return "[]". b. Traverse from head, use a Set to avoid cycling, append values with spaces. c. Return the string representation.
  4. In main, test with different list sizes (n=1, n>1) and k values (k=1, k>1), including edge cases.

Java Implementation

import java.util.*;

public class JosephusProblem {
    // Node class for the circular linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // Solves the Josephus problem
    public int solveJosephus(Node head, int k) {
        if (head == null) {
            return -1;
        }
        if (head.next == head) {
            return head.value;
        }
        Node current = head;
        while (current.next != current) {
            // Move to the node before the one to be eliminated
            for (int i = 0; i < k - 1; i++) {
                current = current.next;
            }
            // Remove the k-th node
            Node nextNode = current.next;
            current.next = nextNode.next;
            current = current.next;
        }
        return current.value;
    }

    // Converts circular linked list to string
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        Set<Node> visited = new HashSet<>();
        while (current != null && !visited.contains(current)) {
            visited.add(current);
            result.append(current.value);
            if (current.next != head) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;
        int k;

        TestCase(int n, int k) {
            this.k = k;
            if (n == 0) {
                head = null;
                return;
            }
            head = new Node(1);
            Node current = head;
            for (int i = 2; i <= n; i++) {
                current.next = new Node(i);
                current = current.next;
            }
            // Make circular
            current.next = head;
        }
    }

    // Main method to test Josephus problem
    public static void main(String[] args) {
        JosephusProblem solver = new JosephusProblem();

        // Test cases
        TestCase[] testCases = {
            new TestCase(4, 2),     // n=4, k=2
            new TestCase(3, 3),     // n=3, k=3
            new TestCase(1, 1),     // Single node
            new TestCase(5, 1),     // k=1
            new TestCase(7, 4)      // Larger n, k
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + solver.toString(test.head));
            System.out.println("k: " + test.k);
            int result = solver.solveJosephus(test.head, test.k);
            System.out.println("Last person remaining: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4
k: 2
Last person remaining: 3

Test case 2:
Input list: 1 2 3
k: 3
Last person remaining: 1

Test case 3:
Input list: 1
k: 1
Last person remaining: 1

Test case 4:
Input list: 1 2 3 4 5
k: 1
Last person remaining: 5

Test case 5:
Input list: 1 2 3 4 5 6 7
k: 4
Last person remaining: 2

Explanation:

  • Test case 1: n=4, k=2, eliminate 2, 4, 1, leaving 3.
  • Test case 2: n=3, k=3, eliminate 3, 2, leaving 1.
  • Test case 3: n=1, k=1, single node 1 remains.
  • Test case 4: n=5, k=1, eliminate 1, 2, 3, 4, leaving 5.
  • Test case 5: n=7, k=4, eliminate 4, 1, 6, 5, 7, 3, leaving 2.

How It Works

  • Node: Stores an integer value (person number) and a next pointer.
  • solveJosephus:
    • Returns -1 for empty lists, head value for single-node lists.
    • Iterates while more than one node remains:
      • Traverses k-1 steps to find the node before the k-th.
      • Removes k-th node by updating next pointer.
      • Moves to the next node.
    • Returns the value of the last node.
  • toString: Traverses from head, uses a Set to prevent cycling, returns space-separated string or "[]".
  • Example Trace (Test case 1):
    • Input: 1→2→3→4→1, k=2.
    • Step 1: current=1, eliminate 2, list=1→3→4→1.
    • Step 2: current=3, eliminate 4, list=1→3→1.
    • Step 3: current=1, eliminate 1, list=3→3.
    • Return: 3.
  • Main Method: Tests different n and k, including single node and k=1.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Solve JosephusO(n * k)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the list.
  • Time complexity: O(n * k) for solveJosephus (n-1 eliminations, each up to k steps); O(n) for toString (traverse list).
  • Space complexity: O(1) for solveJosephus (constant pointers); O(n) for toString (StringBuilder and Set).
  • Worst case: O(n * k) time, O(n) space for output with large lists and k.

✅ Tip: Use the circular linked list’s structure to efficiently eliminate nodes by updating next pointers. Keep track of the current node to continue from the correct position after each elimination.

⚠ Warning: Ensure k is handled correctly for each elimination step, and avoid infinite loops by checking for single-node conditions. Handle edge cases like n=1 or empty lists.