🧠 Problem Summary

The Josephus problem is a classic theoretical problem in computer science and mathematics. It is stated as follows:

Given n people standing in a circle, every k-th person is eliminated in a round-robin fashion. After each removal, counting resumes from the next person. The process continues until only one person remains. The problem is to find the position (1-based or 0-based) of the last remaining person.

For example, with n = 7 and k = 3, the order of elimination is:

Eliminated: 3 → 6 → 2 → 7 → 5 → 1 → Survivor: 4

This general problem can be solved recursively in O(n), but in a special case when k = 2, it admits an O(1) time closed-form solution.

🧩 Intuition (k = 2)

When k = 2, the Josephus problem has a beautiful binary pattern. Here’s what happens:

• People are eliminated in powers of two: the 2nd, 4th, 6th, etc.
• The safe position follows a pattern that can be expressed with binary shifts.

Key Insight:

If n is the total number of people, and L is the largest power of 2 ≤ n, then:

Josephus(n) = 2 × (n - L)

This gives the position of the last remaining person (1-based index).

🧮 C++ Code (O(1) for k = 2)

class Solution {
public:
    int josephus(int n) {
        int l = 1 << (31 - __builtin_clz(n)); // Largest power of 2 <= n
        return 2 * (n - l) + 1;
    }
};

Explanation:

• __builtin_clz(n) returns the number of leading zeroes in n.
• 1 << (31 - __builtin_clz(n)) computes the largest power of 2 ≤ n.

💻 JavaScript Code

function josephus(n) {
    const highestPower = 1 << (31 - Math.clz32(n));
    return 2 * (n - highestPower) + 1;
}

🐍 Python Code

def josephus(n):
    l = 1 << (n.bit_length() - 1)
    return 2 * (n - l) + 1

✅ Final Thoughts

• This elegant O(1) formula only works when k = 2.
• For general k, you need simulation (O(n)) or recurrence (O(n log k)).
• The Josephus problem is a great blend of bit manipulation, recursion, and mathematical pattern recognition.

If you found this helpful, drop a ❤️ and follow for more deep dives into classic CS problems!

Happy problem-solving! 🧠✨