Find the element that appears once others appears TWICE.

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 in a sorted array, where all elements appear twice(one after one) except one element appears only once.

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

Count number of Bits to be flipped to convert A to B 

Count number of Set Bits in Integer. 

Check if number is Power of Two. 

Find all subsets of a set (Power Set). 

Skyline Problem in Java. 

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted 

Count trailing zeros in factorial of a number 

When to use SOAP over REST Web Service. Is REST better than SOAP? 

Tower Of Hanoi Program in Java. 

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.