A Thinking Ape - Circle of People

Inspiration

The resolution was inspired in a circle linked list where we ran through it to eliminate the second "person" until we got the final answer. Based in a pattern we could create a formula to easily find the right answer. To conclude, we used our formula as base to code it.

What it does

It retrieves the right answer of the problem with a number as entry.

How we built it

We build it based in some case tests where we could find a pattern and finally get a formula.

Challenges we ran into

We were challenged by getting the pattern and then to find a formula where it would match all the case tests results.

Accomplishments that we're proud of

Get all the results with one formula.

What we learned

That when we find a pattern in a problem we can find to every single entry its result.

What's next for A Thinking Ape - Circle of People

The next step would be to find a pattern that would change our formula to work regardless the position of the removed "person".

Answer

Straight to the point, the formula is: (n-2^(floor(log(2, n))))×2+1 Explaining how we got to this formula: we are running the List 2 by 2 removing the element for each N+1 elements in the list. The number of the last element would be N+2. The pattern found shows that the number of the last element removed resets every 2ˆx time. Below you can find a Java code that returns the last element in the list given the size of the list n.

Code

    public static int getLastElement(int n) {
        if(n==0) return -1;//Nobody is in the circle
        int logPart = (int) (Math.log(n)/Math.log(2));//Get the Last  2ˆx below N
        int lastElement = (int) (n - Math.pow(2, logPart))*2+1;//Calculate the last element
        return lastElement;

    }

Built With

• java
• word