public class Piirileikki {

    private static int viimeinen(int n) { // O(n)
        int[] t = new int[5*n];
        for (int i = 0; i < n; i++) {
            t[i] = i+1;
        }
        int s = n; // seuraava kohta
        int v = 1; // vika lapsi
        for (int i = 0; i < s; i++) {
            v = t[i];
            if (i%2 == 0) {
                t[s] = t[i];
                s++;
            }
        }
        return v;
    }

    private static int viimeinen2(int n) { // O(log n)
        int k = 1;
        while (2*k <= n) k = 2*k;
        n = n-k;
        return 2*n+1;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 32; i++) {
            System.out.println("viimeinen("+i+") = "+viimeinen(i));
        }
        System.out.println(viimeinen2(1000000000));
    }
}