Amazon Interview Question
AnalystsQuestion as it is written down is ambiguous because is is not clear if numbers, while being un-ordered can be arranged into a continuous sequence. For example this sequence
7 3 5 1 4 4 2 6
has all numbers from 1 to 7 with 4 repeated twice. Summing them up as if there was no duplicated number and subtracting it from a sum of all number will give a duplicate number.
sum(7,3,5,1,4,4,2,6) = 32.
32 - 7*(7-1)/2 = 4.
XORing numbers is another, "tricky" solution I suppose...
However, if numbers in a set are not consecutive like
1, 8, 9, 3, 4, 4, 11, 5
Algorithm described above won't work.
Slight correction to the formula, sum - n * (n-1)/2. Which is in you case, 32 - 8(8-1)/2 = 4
use hashtable to count and store the values along with teir count...then search where count =1..its O(n).
int unique(int *arr , int len)
{
int unique = 0,i = 0;
while(i < len)
{
unique ^= arr[i++];
}
return unique;
}
Hey... Check this out...
public class Dup {
private static int arraySum(int arr[]){
int arrySum = 0;
for(int i = 0; i < arr.length; i++){
arrySum = arrySum + arr[i];
}
return arrySum;
}
private static int arraySquareSum(int arr[]){
int arrySqSum = 0;
for(int i = 0; i < arr.length; i++){
arrySqSum = arrySqSum + (arr[i]*arr[i]);
}
return arrySqSum;
}
private static int naturalSum(int arr[]){
int arrSize = arr.length;
return (arrSize *(arrSize+1))/2;
}
private static int naturalSqSum(int arr[]){
int arrSize = arr.length;
return (arrSize*(arrSize+1)*(2*arrSize+1))/6;
}
private static int duplicate(int arr[]){
int duplicate =0, arrySum=0, arrySqSum=0, natSum=0, natSqSum=0;
arrySum = arraySum(arr);
arrySqSum = arraySquareSum(arr);
natSum = naturalSum(arr);
natSqSum = naturalSqSum(arr);
duplicate = (natSqSum - arrySqSum) / ( 2 * (natSum - arrySum)) - (natSum - arrySum)/2;
return duplicate;
}
private static int missing(int arr[]){
return (naturalSum(arr) + duplicate(arr) - (arraySum(arr)));
}
public static void main(String[] args) {
int arry[] = {7 ,3 ,5 ,1 ,4 ,4 ,2 ,6};
System.out.println("Duplicate Number: "+duplicate(arry));
System.out.println("Missing Number: "+missing(arry));
}
}
public static void getRepeatedElement(int[] a)
{
int i = 0;
int j = a.Length -1;
int n = a.Length;
while (i <= j)
{
if (i < j)
{
if (a[i] != a[j])
{
j--;
}
else if (a[i] == a[j])
{
Console.WriteLine("Repeated:" + a[i]);
break;
}
}
if( i== n-1)
{
Console.WriteLine("All Elements are Unique");
}
if (j == i)
{
j = n - 1;
i++;
}
}
}
Find sum of first n numbers say n = 100.
sum of first n numbers would be (100*101)/2 = 5050
Sum of first n-1 numbers would be (99*100)/2 = 4950
Sum of all elements in the array O(n) complexity = x (say)
find difference 5050 - x = k (say)
Repeated number is 100 - k.
We can find out the duplicate element by using Set, list or trvaersing using loop on array.
Below link can be useful to find out the algorithm to find duplicate or repeated elements in an array in java
<a href="newtechnobuzzz.blogspot.in/2014/07/find-out-repeated-or-duplicate-element.html">Find out duplicate or repeated elements in an array in java</a>
newtechnobuzzz.blogspot.in/2014/07/find-out-repeated-or-duplicate-element.html
Try XOR of all the numbers at 1 go. The final value of the xor of all elements will five you the value which is not repeated.
- Anonymous August 18, 2011