The basic problem here comes from the Josephus Problem. In Josephus problem, N people stands in a circle and every second person is killed until only one person is left in the circle. Then that man is free to go. The problem in Josephus Problem is to find the index of the free man.

We can find the solution of the Josephus problem by a recursive solution. The solution is follow:

J(1) = 1

J(2n) = 2J(n) - 1; when n >= 1 (even case)

J(2n+1) = 2J(n) + 1; when n >= 1 (odd case)

With some pattern finding, and mathematics, we can show that the final result of a Josephus circle will be a cyclic left shift of the binary of N.

If we take some examples:

J(1) = 1

J(2) = 1

J(3) = 3

J(4) = 1

J(5) = 3

J(6) = 5

J(7) = 7

We can see that, J(2m + l) = 2l + 1

Now if we look at the binary of the N. We have something like this.

N = (bm bm-1 ... b1 b0)2

l = (0m bm-1 ... b1 b0)2

2l = (bm-1 ... b1 b00)2

2l + 1= (bm-1 ... b1 b01)2

J(N) = (bm-1 ... b1 b01)2

So, the answer is the cyclic left shift of N

So, if 5 people were standing in a circle, the person to survive is the one with id 3. Example: 5 = (101)2. After one cyclic left shift, 5 becomes 3 = (11)2. So if we start again with 3 people in a circle, cyclic left shift of 3 is exactly 3, so we would stop playing the game. And 3 is thus our lucky number.

So, given N, the lucky number can be found by calculating the number of 1s in its binary form. Let the count be x. So the lucky number is 2x-1

To count how many integers are there, we only have to count how many integers have x 1s in its binary form. This can be done with combinatorics. Then the integers from 1 to 2K-1 has K bits in them.The answer is KCx.


66% Solution Ratio
ragibshahriarEarliest, Apr '20
JUNIORHMMC_CODLightest, 131 kB
bokaifShortest, 245B
Toph uses cookies. By continuing you agree to our Cookie Policy.