Josephus problem

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Mathematical recurrence: J(1)=0; J(n)=(J(n-1)+k)%n. The 0-indexed survivor position builds from n=1.

Algorithm

1pos = 0.
2For i from 2 to n: pos = (pos + k) % i.
3Return pos + 1 (convert to 1-indexed).

Example Walkthrough

Input: n=5, k=2

1.J(1)=0. J(2)=(0+2)%2=0. J(3)=(0+2)%3=2. J(4)=(2+2)%4=0. J(5)=(0+2)%5=2. 1-indexed=3.

Output: 3

Common Pitfalls

•0-indexed formula; add 1 at end for 1-indexed answer.

Josephus problem.java

Java

// Approach: Mathematical DP. J(1) = 0; J(n) = (J(n-1) + k) % n.
// Time: O(n) Space: O(1)
class Solution {
    public int josephus(int n, int k) {
        int[] p = new int[n];
        for (int i = 0; i < n; i++)
            p[i] = i + 1;

        int c = 0;
        int j = 0, s = 1;
        while (j <= n) {
            // System.out.println(j);
            if (c == n - 1)
                break;
            else {
                if (j == n)
                    j = 0;
                else {
                    if (p[j] != 0) {
                        if (s == k) {
                            p[j] = 0;
                            s = 1;
                            c++;
                        } else
                            s++;
                    }
                    j++;
                }
            }
        }

        int r = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] > 0) {
                r = p[i];
                break;
            }
        }

        return r;
    }
}

Was this solution helpful?