Highbridge Capital Interview Question Java Developers
Country: United States
Interview Type: In-Person
nice method , when 2 numbers are missing.
But when n is large, (n*(n+1)/2) will be large and will cause integer overflow. So, we can solve the first case by using the XOR method. Similarly, is there a method to solve for the second case?
DreamCoder's solu for find 1 missing number is perfect.
For multiple missing numbers, you can use counting sort,which takes O(N) spaces.
@rkt, is there a method to solve for the second case?
we can solve using xor.
1. xor of all the elements array and natural number 1 to n+1
Lets say we will get value 1(bit notation 0001)
2. divide the whole elements(array and natural numbers 1 to n+1) into two groups based on 1st bit(since resulting number in step1 has 1st bit 1).
one group of numbers which has all the 1st bits is 1
second group of numbers which has all the 1st bits is 0.
3. apply xor on first group you will get one number
4. apply xor on second group you will get second number.
TC. - O(n+n+n) = O(n)
SC - O(1)
-Devendar
Yes, we can use count sort to find multiple missing numbers from 1 to n or 1 to n+1. for example we have number n = 10 and series 2,5,4,3,1,7,9,10 then if we count sort based or our knowledge that biggest number is 10 then we will get 1,2,3,4,5,7,9,10 hence missing numbers while traversing again will be 6 and 8. This way you can find multiple missing numbers as well instead of solving equations which for 1 missing number is fine.
To know how counting sort works in O(N) time you can watch this video
youtube.com/watch?v=w9njRpeuVew
@Anonymous: I understood the count sorting algo but if you observe carefully, the algo has a bug while displaying the array content that might lead to crash as display goes beyond the array size (until 1024)if size is just 16 in that case!!! Instead I would suggest to use len itself for the outer for loop to counter this bug...
Please correct if i am wrong.
Thanks.
public static int find_miss_one_number(int[] test,int form,int to){
int result1=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
}
int result2=0;
for(int i=form;i!=to+1;i++){
result2+=i;
}
return result2-result1;
}
public static int[] find_miss_two_numbers(int[] test,int form,int to){
int result1=0;
int result2=0;
for(int i=0;i!=test.length;i++){
result1+=test[i];
result2+=test[i]*test[i];
}
int result3=0;
int result4=0;
for(int i=form;i!=to+1;i++){
result3+=i;
result4+=i*i;
}
int sub1=result3-result1;
int sub2=result4-result2;
//x+y=sub1;
//x^2+y^2=sub2;
int a=2;
int b=sub1*(-2);
int c=sub1*sub1-sub2;
int[] result=new int[2];
result[0]=(b*(-1)-((int)Math.sqrt(b*b-4*a*c)))/(2*a);
result[1]=(b*(-1)+((int)Math.sqrt(b*b-4*a*c)))/(2*a);
return result;
}
When one number is missing:
- dreamCoder August 21, 2012find the sum of numbers from 1 to n using the formula... n(n+1)/2. Then the difference between the actual sum and the calculated sum is the missing number
when two numbers are missing:
like above, get equation for a+b=x -------- equation 1
now sum the square the numbers using n(n+1)(2n+1)/6 and then calculate actual value for numbers from 1 to n. Now the difference is in the form of equation a^2 + b ^2 = y ------ equation 2
From these two equations, you can solve for a and b.