DEV Community

Cover image for ⚔️ The Josephus Problem Explained: Constant-Time Solution for k = 2
Om Shree
Om Shree

Posted on

⚔️ The Josephus Problem Explained: Constant-Time Solution for k = 2

#programming #cpp #javascript #python

🧠 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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

🐍 Python Code 

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

✅ 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! 🧠✨

Top comments (4)

Collapse
 
thedeepseeker profile image
Anna kowoski •

Best explanation of Josephus Problem so far.

Collapse
 
om_shree_0709 profile image
Om Shree •

Thanks Anna

Collapse
 
ravavyr profile image
Ravavyr •

These algorithm posts a cool, i like "solving the puzzles".

Are there real world approaches for this one?
Or well, in real world projects, what's a scenario where this algorithm is used?

Collapse
 
om_shree_0709 profile image
Om Shree •

Great question — and love that puzzle-solving spirit! 🧩⚔️

The Josephus Problem does have some real-world analogies, even if it's a bit abstract. It’s often used to model:

  • Circular elimination scenarios, like in load balancing (e.g., killing off jobs in round-robin fashion),
  • Token-passing in distributed systems, where nodes drop out of a ring,
  • Or even game mechanics, like player rotations or survivorship in last-man-standing formats.

It’s also a great teaching tool for mastering modular arithmetic and recursive thinking — skills that transfer directly to real-world algorithmic problem-solving. 💡

Keep solving — these mental puzzles are the best gym for your brain! 🧠🚀