This was an interesting problem given to me by Dada since I am new to puzzles and algos. I am sure you would like this.
Problem
Given an unsorted array A[1...n]. There is one duplicate number in the array which you need to find out.
Solution
We already know that there are n element and there is only one duplicate number.
Lets solve this, we will take the n = 8, means there are 8 elements in array with range of 1…8. Now since there is one duplicate number the actual range of numbers will be 1….[n-1] i.e. 1..7
I assume here that many people would be aware of XOR operators, so we are going to use XOR operators to find the duplicate numbers. But just to take a quick re-cap XOR has the following property
| p | q | p + q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
What next we will do that we will calculate the XOR of the range 1…[n-1] which is 1…7 here. Lets call the result as XOR(range). Now the next thing is to calculate the XOR if the range calculated just now i.e. XOR(range) with the array elements given in the problem. Why we are doing this is because when we will caculate this the number with even occurences will go out and the the only element remaining will be the duplicate which we have to find out. Lets’ check the program now.
Program
package com.bundle.algos;
//In this kind of problems you know the range of the elements
// in this example range is 1-7 and total number of elements is 8
public class FindDuplicateInArray {
static int xorArray,dup;
public static void main(String args[]){
int[] _array = new int[]{1,2,6,3,4,5,6,7};
//int[] _array = new int[]{11,12,13,14,14,15,16};
int duplicate = findWithXOR(_array);
System.out.println(“Duplicate : ” + duplicate);
}
public static int findWithXOR(int[] input){
int xorArray=1;//,dup=0;
for(int i=2; i<=(input.length-1);i++){
xorArray = xorArray ^ i;
//System.out.println(“XOR : ” + xorArray);
}
System.out.println(“XOR Array : ” + xorArray);
for(int k=0;k<=input.length-1;k++){
xorArray = xorArray ^ input[k];
System.out.println(xorArray);
}
//System.out.println(“Duplicate : ” + dup);
return xorArray;
}
}
Complexity of the problem
This will be θ(n) which is the best part of the solution.
This solution is for a known range of 1..n. I will come up with some more generic solutions soon. 
