Tutorial for Odd

Link to original problem: http://www.codechef.com/problems/DCE05

If N was smaller, we could implement a recursive function to compute our answer and this problem would be trivial. However with N as large as 10^6, we can't afford to declare and manipulate an array if we want our program to run within the time limit, and there's a clever way to solve it.

The key to this problem is realizing that the position where we should stand to pass on the first selection must be for sure a multiple of 2. From there on, we will be able to generalize our position after N selections.

1. Numbers left after 1st selection (from now on first iteration)

Does the number of applicants being odd or even matter to our placement?

Actually, as we will see ahead in this analysis, it only matters if the number is a power of 2 or not , we will arrive at that solution by working in a systematic way trough some iterations.

Let A = [1, 2, 3, 4, 5, ... N] with N even to make explanation easier.

* After 1st iteration: [2, 4, 6, 8, ... N]

we see that the numbers on this iteration follow the general pattern:

2 + 2^(k), k starting on 1...

2. Generalizing to the numbers left after Nth iteration

From the above formula and with some fast thinking on a piece of paper, it is possible to deduce which law the numbers on the array after iteration N follow:

2^(N) + (2*N)^(k)

Which tells us 2 very important things:

a) The number should be a power of 2;

b) It doesn't matter how many applicants exist as long as we stand on a position that is a power of 2;

If the number of applicants, N, is itself a power of 2, we must stand on the position 2^(N), else, we need to find a way that allows us to get to the nearest power of 2 possible, from the position we are standing at.

That way involves logarithms of base 2. If N is itself a multiple of 2, then we stand on position 2^(log2(2)), if it is not, we need to get as close as one as we can get, which can be achieved by using the floor function on the log2, to get our final answer: Given a number N, to be selected we must stand on position:

2^floor(log2(N))

Hope this was helpful :)