1
$\begingroup$

I came through Josephus problem a little while ago. Problem is stated as follows :

"People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution."

Though I was able to figure out O(n) (n being no. of people & k being specified no of people skipped) solution to this problem using DP.I came to know that a better solution for larger value of n exists O(k*log(n)),but unable to figure it out.

Please help me with O(k*log(n)) solution.

$\endgroup$
  • $\begingroup$ Better solution than? Where is your question? After citing Josephus problem you have acknowledged the existence of $O(n)$ and $O(k\log(n))$ solutions. Good, well done. $\endgroup$ – Evil May 31 '16 at 4:25
  • $\begingroup$ I am looking for k*log(n) solution. $\endgroup$ – JVJ May 31 '16 at 4:28
  • 1
    $\begingroup$ I understand that you need help with this solution. Do you have it? What is unclear? What do you expect? $\endgroup$ – Evil May 31 '16 at 4:32
  • $\begingroup$ I have checked the magic keyphrase josephus klogn and to my surprise, there is SO answer to it but there was more, here are implementations in several languages (even XSLT). But this might not have been the problem since probably you have seen some (pseudo)code. According to SO, the part where n%k is subtracted is problematic, but you have not asked a question... $\endgroup$ – Evil May 31 '16 at 5:07
  • $\begingroup$ What are $n$ and $k$? The running-time bound smells like "solve on paper, compute the result according to the formula you get". $\endgroup$ – Raphael Apr 29 '17 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.