waidfj's blog

By waidfj, history, 3 hours ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it