Josephus Problem klogn Adjustment

Revision en1, by waidfj, 2026-09-19 21:38:47

Hello! I was studying Josephus Problem (in a circle of n people, each round the kth person is killed until one person is left, find out who survives)

I am aware of the O(n) solution, the recursive and the iterative solutions. I understand that the survivor of the circle is obtained from getting the survivor of the smaller cicle and adjusted by k positions.

However I just found the O(klogn) solution on cp algorithms. I understand that we are skipping n/k steps when k is less than n to save time but I don't understand how is the value of it is adjusted to give the answer for the current circle size?

Would someone be able to help me on this point please?

Tags josephus problem, recursion, math, need help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English waidfj 2026-09-19 21:38:47 1040 Initial revision (published)