5
$\begingroup$

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)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I think that this question is relevant here: cs.stackexchange.com/questions/1218/… $\endgroup$
    – Vitaly Olegovitch
    Mar 3, 2015 at 13:42
  • $\begingroup$ It sounds to me like the interviewer isn't looking for the best computational complexity (It's hard even to come up with a method worse than O(n)), but essentially for the fact that with modular arithmetic your loop only needs to use a single bit of memory to count as it goes through. $\endgroup$
    – mwfearnley
    Mar 4, 2015 at 17:06

5 Answers 5

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ That said, sum all the array elements is not the best way (you could exceed the max_integer). $\endgroup$
    – Fabio Filippi
    Mar 3, 2015 at 15:37
  • 7
    $\begingroup$ @FabioF.: Overflow would not alter the even/oddness of the result $\endgroup$
    – Bergi
    Mar 3, 2015 at 18:56
  • $\begingroup$ @Bergi assuming that your field is $\mathbb{Z}_{2k}$ for $k \in \mathbb{N}$, which is of course the case for signed/unsigned integers, but might not be if you reserved, say, the highest bit pattern for infinity or something. $\endgroup$
    – wchargin
    Mar 4, 2015 at 1:58
  • 4
    $\begingroup$ If you're worried about overflow, just count the number of odd numbers in the array. If that number is even, then the sum of the whole array is even as well. bool function isSumEven(array) { int numOdds = 0; for (int i = 0; i < array.length; i++) { if (array[i] % 2 == 1) { numOdds++; } return numOdds % 2 == 0; } $\endgroup$
    – Pwner
    Mar 4, 2015 at 2:19
  • 1
    $\begingroup$ @Pwner: what if the number of (odd) elements of the array overflows int? :-) $\endgroup$
    – yatima2975
    Mar 4, 2015 at 13:09
12
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Technically you need only count the number of odd, if that count is even the sum will be even if its odd the sum will be odd, regardless of how many evens there are. :) $\endgroup$
    – JustinM
    Mar 3, 2015 at 23:38
  • $\begingroup$ The second paragraph is important. We have an $\Omega(n)$ lower bound but we can certainly save the time for summing (which is non-constant in many cost models)! As the need of others to post further answers indicates, you might want to add you to implement your idea without additions, though. $\endgroup$
    – Raphael
    Mar 4, 2015 at 7:14
7
$\begingroup$

Modulo arithmetics is what you want. Here you need only arithmetics modulo 2, i.e. only look at the last bit of each number, if binary encoding of natural numbers is used, or two's complement representation of positive and negative number. It works with one's complement only for positive integers.

Then you can simply use bitwise XOR for addition, which is somewhat cheaper than doing a real addition.

As proved by hengxin, you have to do it for all elements of your array, so that the algorithm is necessarily linear in the size of the array.

This is no better complexity than other answers, but your question title is best solution. So there is more than complexity to the best solution (else we would be doing matrix multiplications much faster).

Bonus: using modulo arithmetics, or XOR, has the advantage that you do not risk arithmetic overflow as you would by computing the actual sum.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I fail to see what this adds over hengxin's answer. $\endgroup$
    – Raphael
    Mar 4, 2015 at 7:19
  • 1
    $\begingroup$ @Raphael I upvoted hengxin before answering, and I refer to it. But, it seemed wrong that no answer was hinting at modulo arithmetics (my initial motivation). Then, using XOR when possible seems faster than parity test and incrementation (useless for even). OP was asking for best solution, thus the constant matters (cf matrix multiplication). Finally, it is useful to underscore that not doing the sum avoid arithmetic overflow. All these points can be useful in an interview to show knowledge and understanding of all issues. I was not expecting that many votes, but that is SE. $\endgroup$
    – babou
    Mar 4, 2015 at 9:44
  • $\begingroup$ @Raphael Furthermore, as you hint in your own comment. Complexity analysis can use other models of computation. Counting odd numbers can then add a $\log n$ complexity (as you manipulate an increasing counter, that may go up to n), while modulo arithmetics, and especially its XOR implementation, will not. $\endgroup$
    – babou
    Mar 4, 2015 at 9:50
0
$\begingroup$

Of course, you should check all $n$ input elements. But I suppose that person who asked this question wanted from you to find fastest solution(in terms of the cost of the machine operation). What I mean: in fact you do not need to calculate the sum of all elements. You just need to know if it's odd or even.

Suppose you have processed $k$ first elements. Let's denote their sum like $S_k$. In fact we don't know it. Now you process $k + 1$ element. There are 4 possibilities:

  • $S_k$ is odd, and $k + 1$ element is odd then $S_{k+1}$ is even.
  • $S_k$ is odd, and $k + 1$ element is even then $S_{k+1}$ is odd.
  • $S_k$ is even, and $k + 1$ element is odd then $S_{k+1}$ is odd.
  • $S_k$ is even, and $k + 1$ element is even then $S_{k+1}$ is even.

Now we should make a xor operation: $S_k = S_k \text{ xor } (k+1)\text{th element}$. Initially, $S_1$ is equal to the first element. Now if $S_n$'s first bit is $0$ then the sum is even else is odd.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ "to check first bit is much cheaper(in terms of machine operations) then to add two numbers." - Citation needed. What's your evidence? In fact, I expect this will be false. Adding two numbers is one instruction and one CPU cycle (on modern CPUs). Testing whether two bits are equal is more expensive (a branch instruction). Masking out the low bit and then xor-ing is also likely to be more expensive (e.g., 2 instructions instead of 1), but in any case not "much cheaper". So what's the basis for that statement? $\endgroup$
    – D.W. ♦
    Mar 9, 2015 at 17:10
  • $\begingroup$ You are right, we need simply xor two numbers. This will have effect of checking first bit and make necessary decision. $\endgroup$
    – rbtrht
    Mar 9, 2015 at 17:22
  • $\begingroup$ Xor-ing all the numbers in the array (as you suggest) is not likely to be any faster than just summing all the numbers in the array (as the question already mentions). The question asks whether there is any approach that is faster than summing all the numbers in the array; your answer doesn't seem to actually answer that question. $\endgroup$
    – D.W. ♦
    Mar 9, 2015 at 21:26
  • $\begingroup$ I have made tests on a couple machines. You are right. XOR is faster than adding two numbers only on 0.001 ns. It's in insignificant. But I read in many places that xor is faster. I don't understand why this mistake rises in many places. May be you know? $\endgroup$
    – rbtrht
    Mar 10, 2015 at 10:25
-2
$\begingroup$

If you have a usual computer using two's complement arithmetic, just add all the numbers. While you are only interested in the lowest significant bit of the result, the effort of masking out anything else is not going to be worth the trouble.

In theory, you can save time by just fetching and adding (or xoring, which is equivalent for the lowest significant bit) the lowest significant byte of each number. In practice, the memory interface and cache lines will deliver all of them anyway.

Any input number can change the result or not, so you don't get around accessing any element anyway.

In short: this is one task where the simplest brute-force solution cannot be beat. At least while we are talking about a single CPU.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This adds nothing to the answers that were posted before it. $\endgroup$
    – David Richerby
    Mar 19, 2015 at 17:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.