What is the best solution to find whether the sum of an array is even or odd

Problem Detail: 

I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really interested in the actual sum, I just want to know whether it's even or odd.

Or how do I prove that it cannot be done better than $O(n)$?

Asked By : avi

Answered By : Juho

Consider e.g. an array that consists of all zeros except for the last element, which is either an odd integer or an even integer. To decide whether the sum of the $n$ elements is even or odd, you must read the whole input, i.e. check even the last index of the array. So you must perform at least $n$ steps.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40019