Скачать или смотреть Josephus Problem | Recurrence + Iterative Optimization Explained | GFG POTD 24 Jan 2026

GFG POTD (24th Jan 2026)

Educational Insight

The "Josephus Problem" encodes a circular elimination process into a compact recurrence, making it a staple for mastering recursion and mathematical reasoning in algorithms.

The key idea is that after each person is removed, the survivor index for n people can be derived from the survivor index for n−1 people plus a fixed shift of k positions.

Key Implementation Details

Recursive form: J(n, k) = (J(n−1, k) + k − 1) % n + 1 with J(1, k) = 1.

Iterative approach: start ans = 0 (0‑based) and update ans = (ans + k) % i for i from 2 to n, then return ans + 1.

Works efficiently for large n and arbitrary k in O(n) time, O(1) extra space.

Special-case optimizations exist when k = 2 using bit tricks and powers of 2.

Full platform dropping soon. Stay tuned.
Join the waitlist: https://www.visuallyinclined.in/waitlist

#DSA #GFG #Coding #VisuallyInclined