Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: Phone Interview
This is a nice solution. To make it clearer, we can say that we XOR the index of each slot with the value in the slot of the array. Finally we XOR with 'n', the size of the array. The result would be the missing one.
In my profiling experiments I have found XOR and Integer taking same time.
A comparison of N(N+1)/2 and Sum(arr) will have total of N+1 operations.
N inividual XORs and then again XORing them N-1 times making total operations as 2*N-1.
Can you please point why doing XOR would be preferable?
this is not so clear ......
please can any one elaborate the concept
thanks in advance .....
Keep a variable sum and loop through the array - summing up all the elements: sum = sum + a[i] .
Missing number = (n*(n+1)/2) - sum
O(n) complexity .
The answer will still be correct even if an overflow happens, since the integer values will simply wrap around and keep counting. In fact, even if (n*(n+1)/2) is a negative value because of overflow and sum is a large postive value, the subtraction of (n*(n+1)/2) - sum will "re-underflow" to the correct answer.
Every one has given solution , thinking in mind that array startes from 1 to N, but what happens if array start from may be 2,3,...
Not 1 to N but 0 to N. And the assumption is given in the question.
How to find a missing value in an size N unsorted array (value from 0 to N but missing one of them).
I am not a CS major. Can someone please tell me how this code is compared with others in terms of performace?
int temp[N+1];
for (int i=0;i<N;i++)
{
temp[arr[i]]=1;
}
While (temp[i]) {i--;}
return i;
Your solution has linear time complexity.
But it also has linear space complexity.
P.S. I don't think your code could be compiled because in case of non-constant N you need to allocate memory for your temp array dynamically. And if you allocate additional memory dynamically it will affect performance of your solution.
public class findMissingElement {
public static void main(String args[]){
// For sample input 0,5,2,3,1,4,6,10,8,9 where N is 10
int[] iparr = {0,5,2,3,1,4,6,10,8,9};
int sum = 0,s=0,max =0;
for (int i =0;i<iparr.length;i++)
if (iparr[i] >max)
max = iparr[i];
for (int i =0;i<=max;i++)
sum = sum + i;
for (int i =0;i<iparr.length;i++)
s = s + iparr[i];
System.out.println("Missing Element "+(sum-s));
}
Binary search. Suppose we have a list:
[1, 2, 3, 5, 6, 7, 8, 9] so length = 8
Divide the list into 2: [1, 2, 3, 5] and [6, 7, 8, 9], we know that the length is 8/2 = 4.
We can check to see which list is missing a number by checking 'first element' + length - 1 == 'last element', i.e. 6 + 4 - 1 = 9 but 1 + 4 - 1 == 4 != 5, so the left list contains the missing number.
Rinse an repeat, identify [3, 5] as having the missing element. Missing number is the average of the two.
Complexity: O(log n) (I think..)
The problem states that the array is unsorted, but this seems like a reasonable approach for the sorted case.
If we need to find one missing value from N successive numbers we can XOR all values that we have with each other and with numbers from 0 to N. And because:
- J. March 29, 2013a xor a = 0
a xor 0 = a
(a xor b) xor b = a
as a result we will have our missing number.
It has the same time complexity as the solution with finding sum but we won't get overflow.