Java Program taking up too much memory

Question

This is my Problem for which i made the program

Ali baba did a trick on the forty thieves and was able to trap them inside a big cave which was the home of wild wolves. The thieves are without any weapons, only the chief of the thieves has knife. With no weapons they will not be able to fight with the wolves, so they decide to kill themselves rather than being eaten alive.

They all decide that they will stand in a circle and they every third person will kill himself but the chief of the thieves does not like this idea and has no intention of killing himself. He calculates where should he stand so that he is the last one left.

HackerMan wants to build a game based on this story, but instead of killing he decides that the participant will leave the game, and instead of every 3rd position it will be every 2nd position. Of course the number of participants will be much more than 40 in this game.

Input

The first line of input is an integer N (1 <= N <= 1000) that specifies the number of test cases. After that every line contains an integer X (5 <= X <= 100000000) which is the number of participants in the game.

Output

For each test case generate a line containing the position of the participant who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.

Sample Input

3 5 11 45

Sample Output

3 7 27

Here is my Solution Program

class SurvivalStrategy {

    public int next;
    public int value;
    public boolean alive;

    SurvivalStrategy(int n, int v)
    {
        this.next = n;
        this.value = v;
        this.alive = true;
    }

    public int getNext(){
        return this.next;
    }
    public void kill(){
        this.alive = false;
    }

    public void changeNext(int n){
        this.next = n;
    }


    public static void main(String[] args) throws IOException {

        System.out.println("Enter the number of cases");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int[] array = new int[N];
        for(int a = 0; a < N; a++)
        {
            System.out.println("Enter No. of theives in case " + (a + 1));
            array[a] = Integer.parseInt(br.readLine());
        }
        for(int b = 0; b < N; b++)
        {
            try{

                int theives = 0;
                theives = array[b];
                SurvivalStrategy[] people = new SurvivalStrategy[theives];
                int i = 0;
                int nextctr = 2;
                for(i = 0; i < people.length; i++)
                {
                    people[i] = new SurvivalStrategy(nextctr, i + 1);

                    if(nextctr > people.length)
                    {
                        people[i] = new SurvivalStrategy(1, i + 1);
                    }
                    nextctr++;
                }

                int k = 0;
                int nextguy = 0;
                int survivers = people.length;
                boolean CarryOnJatta = true;
                int lastSurviver = 0;
                while(CarryOnJatta)
                {
                    if(k >= people.length)
                    {
                        k = 0;
                        k = k + 2;
                    }
                    if(people[k].alive)
                    {
                        //System.out.println(people[k].value + " is Alive");
                        nextguy = people[k].getNext();
                        if(people[nextguy - 1].alive)
                        {
                            people[nextguy - 1].kill();

                            people[k].changeNext(people[nextguy - 1].next);
                            lastSurviver = people[k].value;
                            survivers--;
                        }else{
                            k = k + 2;
                        }
                        k = k + 2;
                    }else{
                        k = k + 2;
                    }

                    if (survivers == 1)
                    {
                        CarryOnJatta = false;
                        System.out.println("" + lastSurviver);

                    }
                }




            } catch(Exception e)
            {
                e.printStackTrace();
            }
        }
    }
}

My program is giving an output for small values but not for large ones. if i try it with the input(23987443) i get java heap size exceeded error. is there any way i can improve the space as well as time complexity of this program. i am open for other algorithms also if they are generating the desired output.

Answer 1

you could use a circular LinkedList. Add your nodes to the list, and use the counting algorithm to traverse the list. Everytime someone loses, simply call a remove on that person, which will mark it eligible for garbage collection (assuming the list contains the only ref to your node).

Better yet, no need to add everyone all at once on the first cycle through the list. You can simply not add someone if they are a multiple of V iterations. This should chop your memory usage up quite a bit.

This will save space on your heap, since you are maintaining a max size of N, but will have more allocation / deallocation overhead. Still, linkedList.remove offers O(1) complexity. I think it would clean your code up a lot to and make it easier to understand

Answer 2

You are allocating at least 23987443 * sizeof(SurvivalStrategy) memory on the heap - that would be around 300MB per single case, and that is only before this line of code:

SurvivalStrategy[] people = new SurvivalStrategy[theives];

I guess the challenge was designed to teach you with merits of efficient memory handling - so instead of allocating the whole memory at once, you need to process your items one by one, so that you allocate only a few items at a time, letting the no-longer-needed ones to be collected by GC.

Answer 3

You could try to assign more memory to the JVM, there's a recent post about this: Java Heap Space error from command line