CODEWITHSUNDEEP
javaalgorithmsequence
Sufiyan Al-Yousufi
Sufiyan Al-Yousufi

Reputation: 51

How to generate a sequence created by removing all odd-indexed elements recursively from an Arraylist so that we get only 1 element at the end?

I have a list of numbers in an ArrayList. I am trying to remove odd indexed numbers from the list. We need to perform this operation in a loop till it remains only 1 element in the list.

Example:
List -> {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}
List after removing odd-indexed elements after
Iteration 1 : {2, 4, 1, 3, 5}
Iteration 2 : {4, 3}
Iteration 3 : {3}

Brute Force method is working but is there any other way? The number of elements in the list could be huge until 10^18.

private static int getLastNumber(ArrayList<Integer> list)
    {
        int size = list.size();
        for (int i = 1; i<=size; i++) {
            if (i%2 != 0) {
                list.set(i-1, -1);
            }
        }
        for (int i = 0; i<list.size(); i++) {
            if (list.get(i) == -1) {
                list.remove(i);
            }
        }
        if (list.size() == 1) {
            return list.get(0);
        } else {
            return getLastNumber(list);
        }
    }

Upvotes: 0

Views: 454

Answers (1)

Marco Luzzara
Marco Luzzara

Reputation: 6046

It is pretty easy actually: given a list of elements, the returned index is the power of two nearest but less than the size of the list.

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
...

You can do this easily with a bit mask:

public static int getIndex(int a){
    for (int i = 31; i >= 0; i--) {
        if (((a >> i) & 1) == 1)
            return i;
    }

    return 0;
}

public static void main(String []args){
    int a = 10;

    double index = Math.pow(2, getIndex(a));
    System.out.println(index);  
}

Not that easy to prove, at least for me. This can help you to better visualize it:

level
0        1  2  3  4  5  6  7  8  9  ...
1           2     4     6     8
2                 4           8
3                             8

It is like every time you iterate, you are keeping the multiple of 2^level

Upvotes: 6

Related Questions