waidfj's blog

By waidfj, history, 2 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?

Full text and comments »

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