Program efficiency and java.lang.OutOfMemoryError: Java heap space

Question

The problem is to remove every 2nd element until the last one remains. (Assuming the elements are placed in circle)

My program works fine for small values of n but when i use a large value it gives me a java.lang.OutOfMemoryError: Java heap space message.

Can some help me out as to what I need to do to make my code more efficient and solve this error.

Thank You!

import java.util.*;

public class ArrayLists {
    public static void main(String[] args) {
        ArrayList myList = new ArrayList();
        int n = 23987443;
        for (int i = 1; i <= n; i = i + 2) {
            myList.add("" + i);
        }

        Object x = myList.get(myList.size() - 1);
        Object y = myList.get(myList.size() - 1);
        while (myList.size() != 1) {
            if (x == y) {
                for (int i = 0; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            } 
            else {
                x = y;
                for (int i = 1; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            }
            y = myList.get(myList.size() - 1);
        }
        System.out.println("Winner:" + myList);
    }
}

Answer 1

The answer to your problem can be computed with a closed form, for if you write the number of elements in your list as follows:

n = 2^m + l

where m is the largest power of 2, such that 2^m <= n

then the winner is w = 2*l + 1.

So here is a more efficient program:

public class ArrayLists {
  public static void main(String[] args) {
    int n = 23987443;
    int pow = Integer.highestOneBit(n);
    int l = n - pow;
    System.out.println("Winner:[" +((2*l)+1)+"]" );
  }
}

The answer for that value of n:

Winner:[14420455]

To be honest I did not come up with the solution myself, but remembered reading about the Josephus problem in the book "Concrete Mathematics" (Google will find a PDF, check out section 1.3)