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.