ATA - Circle Challenge closed formula

First, we can see that only odd numbers can be the answer, since you have to remove every other element (meaning all even number will be out).

Then, solving the problem for increasing bigger N's, you can see that we have the solution as being the following:

for (1-2) and (1-3) lists, the solutions are (1,3)

for (1-4), (1-5), (1-6), (1-7) the solutions are (1,3,5,7)

for (1-8), (1-9), (1-10), (1-11), (1-12), (1-13), (1-14), (1-15) the solutions are (1,3,5,7,9,11,13,15)

So we have that the solutions are subsets of the list of odd numbers, but with a periodicity.

The periodicity is based on powers of 2. That is, the first period is size 2, the second is size 4, the third is size 8, and so on...

So, given a number, we must find where it lies with regard to the period. This can be accomplish by figuring out the nearest power of two that is less than N : floor(log_2(n)) Then it is just a matter of figuring out where the number lies in respect to the list of odd numbers... so we have the following formula:

F(N) = (N - 2 ^ (floor(log_2(N))) ) + 1

Built With

• brain
• math