Interview - Write a program to remove even elements

Question

I was asked this today and i know the answer is damn sure simple but he kept me the twist to the last.

Question

Write a program to remove even numbers stored in ArrayList containing 1 - 100.

I just said wow

Here you go this is how i have implemented it.

ArrayList source = new ArrayList(100);
for (int i = 1; i < 100; i++)
{
    source.Add(i);
}


for (int i = 0; i < source.Count; i++)
{
    if (Convert.ToInt32(source[i]) % 2 ==0)
    {
        source.RemoveAt(i);
    }
}

//source contains only Odd elements

The twist

He asked me what is the computational complexity of this give him a equation. I just did and said this is Linear directly proportional to N (Input).

he said : hmmm.. so that means i need to wait longer to get results when the input size increases am i right? Yes sirr you are

Tune it for me, make it Log(N) try as much as you can he said. I failed miserably in this part.

• Hence come here for the right logic, answer or algorithm to do this.

note: He wanted no Linq, No extra bells and whistles. Just plain loops or other logic to do it

Answer 1

I dare say that the complexity is in fact O(N^2), since removal in arrays is O(N) and it can potentially be called for each item.

So you have O(N) for the traversal of the array(list) and O(N) for each removal => O(N) * O(N).

Since it does not seem clear, I'll explain the reasoning. At each step a removal of an item may take place (assuming the worst case in which every item must be removed). In an array the removal is done by shifting. Hence, to remove the first item, I need to shift all the following N-1 items by one position to the left:

1 2 3 4 5 6...
<---
2 3 4 5 6...

Now, at each iteration I need to shift, so I'm doing N-1 + N-2 + ... + 1 + 0 shifts, which gives a result of (N) * (N-1) / 2 (arithmetic series) giving a final complexity of O(N^2).