Missing/Repeating Element in an array

Find duplicate element or/and missing element in an array in the following cases--------
One Duplicate / Missing + Range Given

0) First Missing Positive Number
Given an unsorted integer array, find the first missing positive integer. For example, given [1,2,0] return 3 and [3,4,-1,1] return 2.
http://www.programcreek.com/2014/05/leetcode-first-missing-positive-java/

i) One Missing No Repeating
You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
Example:
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5
http://www.geeksforgeeks.org/find-the-missing-number/

Method 1: Sum Formula
1. Get the sum of numbers
       total = n*(n+1)/2
2  Subtract all the numbers from sum and
   you will get the missing number.

Modified Program to avoid Integer overflow:
int getMissingNoUpdated (int a[], int n)
{
    int i,j=1, total=0;
   
    for ( i = 0; i< n; i++, j++) {
    total += j-a[i]; //pick one number from known numbers and subtract one number from given numbers to avoid integer overflow
}
     
    return abs(total);
}

Variation :
All Repeating Even number times except One
You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.
http://www.geeksforgeeks.org/find-the-number-occurring-odd-number-of-times/
http://www.geeksforgeeks.org/find-the-element-that-odd-number-of-times-in-olog-n-time/

ii) One Repeating & One Missing
You have an array of size n which stores integers from 0 to n-1.
In this array one number is a duplicate, that means one is missing.
How can we find duplicate and missing ?
http://www.geeksforgeeks.org/find-a-repeating-and-a-missing-number/

iii) Two Repeating-rest unique
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers. 
http://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/

Variation:
More than Two Repeating:
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space. How to remove duplicate data from an array efficiently? Provide more solutions in the form with additional memory with O(n), O(n²) and O(nlogn).

http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

iv)Two Non Repeating-Other Repeated
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/

Variation 1:
Find even occurring elements in an array of limited range
http://www.geeksforgeeks.org/find-even-occurring-elements-array-limited-range/

v)Two Missing Numbers
http://www.geeksforgeeks.org/find-two-missing-numbers-set-1-an-interesting-linear-time-solution/

-----------------------------------------------------------------------------------------------------------------
Given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]
Answer: 5
http://www.geeksforgeeks.org/find-the-element-that-appears-once/

Variation 1:
You have an array of integers, such that each integer is present an odd number of time, except 3 of them. Find the three numbers.
http://codereview.stackexchange.com/questions/36842/find-elements-occurring-even-number-of-times-in-an-integer-array
Variation 2:
Print All Distinct Elements of a given integer array
Given an integer array, print all distinct elements in array. The given array may contain duplicates and the output should print every element only once. The given array is not sorted.
http://quiz.geeksforgeeks.org/print-distinct-elements-given-integer-array/
Variation 3:
Finding unique numbers from Sorted array in less than O(n)
http://stackoverflow.com/questions/26958118/finding-unique-numbers-from-sorted-array-in-less-than-on

Strategy:
The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

Code:
int main()
{
   int B[] = {1,1,1,3,3,3,20,4,4,4};
   int ones = 0 ;
   int twos = 0 ;
   int not_threes, x ;

   for( i=0; i< 10; i++ )
   {
            x =  B[i];
            twos |= ones & x ;
            ones ^= x ;
            not_threes = ~(ones & twos) ;
            ones &= not_threes ;
            twos &= not_threes ;
   }
   printf("\n unique element = %d \n", ones );
   return 0;
}