ATA Circle Challenge - Java

//

/**

• @author Daniel Corrêa Tucunduva (daniel.tucunduva@gmail.com)
• date: 21/May/2016
• My answer to the A Thinking Ape Algorithm Challenge, part of the Vanhackathon *
• I came upon this solution by manually listing N and f(N) for N from 1 to 16 in Excel. A pattern became apparent,
• with a sequence of odd numbers that restarts every time it reaches a power of two.
• I then realized that the f(N) can be seen as 1 + twice the difference between N and the closest previous power of
• two (when the sequence of f(N) is reset). From there it was just a matter of expressing these realizations
• mathematically. *
• I would like to stress that I had never seen this problem before, and I devised this solution alone, without any aid. *
• The log2asInt function can be made faster using environment-specific, "tricky" logic.
• However, I opted for the mathematically sound and universally valid solution, since the main goal here
• is to display my reasoning. */

package vanhackathon;

public class Vanhackathon {

/**
 * Returns the base two logarithm of an integer as an integer (chops off decimal part using typecasting)
 * @param n greater than zero
 * @return the logarithm as an integer
 * @throws IllegalArgumentException
 */
public static int log2asInt(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return (int)(Math.log(n)/Math.log(2));
}


/**
 * Given a circle of N people and removing every second person until one person is left,
 * returns the position of the person left 
 * @param n greater than zero
 * @return the position of the person left, from 1 to n
 * @throws IllegalArgumentException
 */
public static int vanhackathonChallenge(int n){
    if (n <= 0)
        throw new IllegalArgumentException();
    if (n == 1 || n == 2)
        return 1;
    int log2ofN = log2asInt(n);
    int closestPowerOf2equalOrSmallerThanN = (int)Math.pow(2, log2ofN);
    return 1 + 2 * (n - closestPowerOf2equalOrSmallerThanN);
}     


/**
 * Prints a small test of the vanhackathonChallenge function
 */
public static void main(String[] args) {
    System.out.println(" author: Daniel Corrêa Tucunduva (daniel.tucunduva@gmail.com)");
    System.out.println(" date: 21/May/2016 \n");
    System.out.println(" N, last person remaining:");
    for (int n = 1; n < 129; n++){
        System.out.println(" " + n + " , " + vanhackathonChallenge(n));
    }    
}

}

//