In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (like here).

I want to find out the number of times the circle will be traversed completely (ie the number of times the you will have to go through the entire array).

Note that k can be larger than the size of the circle (if not at the starting, at least after the circle is sufficiently reduced); in the circle maybe traversed completely before the next elimination.


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.