@@ -0,0 +1,2481 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A/**%0A * There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other%0A * number afterward until you reach the end of the list.%0A * %3Cp%3E%0A * Repeat the previous step again, but this time from right to left, remove the right most number and every other number%0A * from the remaining numbers.%0A * %3Cp%3E%0A * We keep repeating the steps again, alternating left to right and right to left, until a single number remains.%0A * %3Cp%3E%0A * Find the last number that remains starting with a list of length n.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * Input:%0A * n = 9,%0A * 1 2 3 4 5 6 7 8 9%0A * 2 4 6 8%0A * 2 6%0A * 6%0A * %3Cp%3E%0A * Output:%0A * 6%0A */%0Apublic class EliminationGame %7B%0A%0A    private EliminationGame eg;%0A%0A    /**%0A     * Calculate the start point of next round with:%0A     * The start point of this round, the step, the number of removed integers.%0A     * If from left, start = start + step * len - step / 2%0A     * If from right, start = start - step * len + step / 2%0A     * step / 2 is actually the step of last round.%0A     * Stop when only one integer remain.%0A     */%0A    public int lastRemaining(int n) %7B%0A        int start = 1;%0A        int step = 2;%0A        int len = n;%0A        boolean isFromLeft = true;%0A        while (len != 1) %7B%0A            len %3E%3E= 1;%0A            if (isFromLeft) %7B%0A                start = start + step * len - step / 2;%0A            %7D else %7B%0A                start = start - step * len + step / 2;%0A            %7D%0A            step %3C%3C= 1;%0A            isFromLeft = !isFromLeft;%0A        %7D%0A        return start;%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        eg = new EliminationGame();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        Assert.assertEquals(1, eg.lastRemaining(1));%0A        Assert.assertEquals(2, eg.lastRemaining(2));%0A        Assert.assertEquals(2, eg.lastRemaining(3));%0A        Assert.assertEquals(2, eg.lastRemaining(4));%0A        Assert.assertEquals(2, eg.lastRemaining(5));%0A        Assert.assertEquals(4, eg.lastRemaining(6));%0A        Assert.assertEquals(4, eg.lastRemaining(7));%0A        Assert.assertEquals(6, eg.lastRemaining(8));%0A        Assert.assertEquals(6, eg.lastRemaining(9));%0A        Assert.assertEquals(8, eg.lastRemaining(10));%0A        Assert.assertEquals(8, eg.lastRemaining(11));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        eg = null;%0A    %7D%0A%7D%0A

add Elimination Game