Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.