What is the best solution to find whether the sum of an array is even or odd
By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.

The adversary argument tells that in theory you have to check each element. By the way, it does not mean you have to sum them up. You can simply count the numbers of even numbers and odd numbers (or go through the array by +1 for even and -1 for odd).