Find the element that appears once others appears TWICE.

Given an array of integers. All numbers occur twice except one number which occurs once. Find the number in O(n) time & constant extra space.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Input: {2, 3, 5, 4, 5, 3, 4}
Output: 2

Input: {2}
Output: 2

Input: {2,1,2}
Output: 1

Algorithm

This problem can be solved in multiple ways but solution might not fulfill time and space complexity constraints given in problem statement.

Time complexity to solve this problem should not be greater then O(n)
Space complexity to solve this problem should not be greater then O(1)

Bit Manipulation will be helpful in this situation.

Before proceeding further lets just see XOR operation and facts.

Lets see some XOR operation,
1.   5 ^ 5     = 0101 ^ 0101 = 0000
2. 1 ^ 1     = 0001 ^ 0001 = 0000
3.   10 ^ 10 = 1010 ^ 1010 = 0000
From the above few operation, we can see that when a number is XOR with same number then result is 0.

Also XOR is Associative and Commutative, it means
Associative    = giving the same result regardless of grouping, i.e. so that a*(b*c)=(a*b)*c
Commutative = independent of order; as in e.g. "a x b = b x a"

1. 1 ^ 1 = 0
2. 1 ^ 1 ^ 2 ^ 2 = 0
3. 1 ^ 2 ^ 1 ^ 2 = 0

Irrespective of order, when a same number will be XOR twice then result will be 0.

So, Now lets see our original problem statement.
Given an array of integers. All numbers occur twice except one number which occurs once. Find the number.

Let's take a small example, say given array is,
1. {1, 1 , 2}
Answer is 2 here, how to find that is simple, simply XOR all the numbers. result will be the number that appeared only once.
From the fact we saw that when a number is XOR with same number then result is 0.
= (1 ^ 1) ^ 2
= (0) ^ 2
= 2
Number that appear only once is 2.

Now, if the given array is {1, 2, 1} or {2, 1, 1}, result will be 2 as we know XOR operation is both
Associative and Commutative.

Java Program to Find the element that appears once.

package javabypatel;

public class FindElementThatAppearOnceRestAllAppearTwice {

 public static void main(String[] args) {
  int arr[] = {6, 2, 5, 10, 5, 2, 10};
  System.out.println(findElementThatAppearOnce(arr));
 }

 private static int findElementThatAppearOnce(int arr[]){
  int result = 0;
  for (int i=0; i<arr.length; i++){
   result = result ^ arr[i];
  }
  return result;
 }
}

Find the element that appears once others appears TWICE.