Find the Number Occurring Odd Number of Times

Question : 

You are given an array of integers. All integers in the array appear exactly twice except one integer. Your goal is to find and return that integer. For example if you have an array 1,2,3,4,4,3,2,1,7,9,9 you have to return number 7.

Approach : 

When I first encountered this question in an interview I said we can use a HashMap. Iterate the array and store the integers in the Map with key as the integer itself and value as the count of number of times the integer occurs in the array. Then simply iterate the HashMap and return the key with value equal to one. 

Time Complexity -> O(N)

Space Complexity -> O(N)

But there is a better approach - one that involves no extra space. 

Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences i.e 1 in our case.

Later I found out that it is very common question asked.   The questions is

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.(GeeeksForGeeks) 

You can see the simple C solution in above link. Below code is for the original question I encountered. So simply xor all the values and return the result.

Code :

package Arrays;

/**
 * Created by Aniket on 3/26/14.
 */
public class SingleCountElementFinder {

    public static int returnNumber(int[] array){

        int no = array[0];

        for(int i=1;i<array.length;i++){
            no = no ^ array[i];
        }

        return no;

    }


    public static void main(String args[]){

        int[] array = new int[]{1,2,3,4,4,3,2,1,7,9,9};
        System.out.println("Single occurring element : " + SingleCountElementFinder.returnNumber(array));

    }

}

Output : 

Single occurring element : 7

NOTE : If you did not know already XOR operation return true if the inputs are different and false if they are same. So if you XOR a number with itself you will get back 0. And if you XOR any number with 0 you get back that number. So in above question each pair of same numbers when XORed gives 0 and finally when XORed with a single instance of the number gives back that number.