anonymouse
BAN USER1. If length of array = n, ActualSum = n*(n+1)/2 ; ActualProd = n!
2. We can obtain sum and prod of given array in linear time
3. We have two unknowns to solve: (1) the repeating element, (2) the missing element
4. We have two equations to solve
The following code returns the missing element:
public static int missingElem(int[] A)
{
int len= A.length;
int sumArray = 0;
int prodArray = 1;
int actualSum = 0;
int actualProd = 0;
int elem=0;
for (int i = 0; i < A.length; i++) {
sumArray+=A[i];
prodArray*=A[i];
}
actualSum = (len*(len+1))/2;
actualProd = factorial(len);
elem = (actualProd * (sumArray-actualSum))/(prodArray - actualProd);
return elem;
}
public static int factorial(int num)
{
if(num==0)
return 1;
return num*factorial(num-1);
}
yup..probably a grep/find followed by uniq
- anonymouse December 07, 2012
Could someone justify this step :
- anonymouse December 10, 2012if(arr[mid] >(arr[low] + mid - low) )