Why does it happen? (Problem — 1)

Revision en7, by slow.coder, 2015-09-28 09:34:12

LuckyLand Lottery is a problem directly related to Josephus problem!!!

In short:

There are N peoples (N > 0) arranged in a loop (peoples are numbered from 1 to N) so that 1st person comes after Nth person. In each lottery round the 2nd person wins starting from random number P (0 < P <= N), then next round starts from that position where it was ended before (winners will not consider for next rounds). Given the value of N and P. You need to find the person who wins at last.

AC soln:

N - 1's complement of(N) + P - 1

I don't know how does it work...

Have you any Explanation to describe this soln?

Tags josephus problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English slow.coder 2015-09-28 09:36:07 39
en7 English slow.coder 2015-09-28 09:34:12 1 Tiny change: 'e _(winner will not ' -> 'e _(winners will not '
en6 English slow.coder 2015-09-28 09:33:44 52 (published)
en5 English slow.coder 2015-09-28 09:31:03 8
en4 English slow.coder 2015-09-28 09:29:53 137
en3 English slow.coder 2015-09-28 09:24:48 32
en2 English slow.coder 2015-09-28 09:24:02 6
en1 English slow.coder 2015-09-28 09:23:03 627 Initial revision (saved to drafts)