CareerCup

take an array containing elements till 50. XOR this array with the given array in which 2 elements are missing.
find the right most bit set in the XOR.
now divide the elements in the given array and the array containing all 50 elements in to two groups such that if the right most bit set in the XOR is also set in the element it will go to one group and if its not set it ll go another group.
Xor the 2 groups individually.
XOR1 and XOR2 will be the two missing numbers.

Question is not clear ! can u please elaborate it ?

xor 3 times.
O(n) time O(1) space No overflow.

I guess array has 1 to 50 but two are missing.

So expanding on hunt's comment...

XOR array with 1,2,... ,50.

if missing numbers are a and b, we get a XOR b.

Using this, we can now tell a bit on which they differ.

Use that bit to partition array into two parts.

XOR each partition individually with 1 to 50 keeping that bit in mind. You will end up with a & b.

@above....the solution might be wrong..suppose 10 and 11 r missing..and if we XOR all the values frm 1 to 50...u will get 50 as O/P...

any one having answer to above ?

I think if we just XOR the array of 50 with an array of 50 zero's. Only the missing values will return 1. The rest of the values will be not equal to 1. example 50 xor 0 / 20 xor 0 / 5 xor 0 will never be 1. only 0 xor 0 = 1

@Divz, 0 xor 0 is 0 not 1 ,,, but 1 ^ 1 is 0,,

and secondly ,we have to solve it without using any other storage (array) and without using addition and subtation method..I am still not able to understand the solution provided by Anonymous ,
@Anonymous , can u plz explain ur solution with a example ,
Thanks
Aloke

@aloke. Your right... It was a stupid mistake on my part.
I think if we XOR the array with 1,2,3,4... 50 individually in an iteration if 1 is present one of the elements with value '1' in the array is 0,similarly if 2 is present again we have one of the elements of the array as zero and so on. For the missing number no element of the array will result in a zero.

I cannot understand this XOR method. Can any one explain it in more detail ?

Another solution could be to sort the array. But this will take O(n) time

Can anyone please explain this solution?

what abt sort n binary search kind of analysis?

Do a summation of numbers from 1 to 50 as SumTill50 = 1+2+...+49+50. Add the numbers in the array SumArray = arr[0] + arr[1] + .. + arr[49] + arr[50]

Substract SumArray from SumTill50 as SumResult = (SumTill50 - SumArray). The result will contain sum of missing numbers.

Do a multiplication of numbers from 1 to 50 as MulTill50 = 1* 2* 3.. *49*50. Multiply the numbers in array MulArray = arr[0] *arr[1] * arr[2]... *arr[49]*arr[50]

Substract MulArray from MulTill50 as MulResult = (MulTill50-MullArray). The result will contain product of missing numbers.

So we are reduced to 2 equations and we need 2 find two unknows
x+y = SumResult
x*y=MulResult

Multiply 1st eq with y
x*y + y*y = SumResult*y

Substract 2nd eq from 1st

y*y = SumResult*y - MulResult - Determine y
Substract value of y from SumResult - Determine x

void missingNums(vector<int>& a, int n){
    vector<int> b(n);
    iota(b.begin(), b.end(), 1);

    int x = 0;
    for(int i:a){
        x ^= i;
    }
    
    for(int i:b){
        x ^= i;
    }
    
    x = x & (~(x-1));
    
    int p = 0,q = 0;
    for(int i:a){
        ((x&i) == x)? (p ^= i) : (q ^= i) ;
    }
    cout << "-----" << endl;
    for(int i:b){
        ((x&i) == x)? (p ^= i) : (q ^= i) ;
    }
    
    cout << p << " " << q << endl;
}