CareerCup

the missing number = xor all numbers from both stacks

i think adding the contents of both the stacks and subtracting one frm the oder can be one soln..

Adding numbers is probably fastest if only 1 number is missing.
Worse ways:
Sort 2 stacks then walk them.
Hash the numbers in the smaller stack then walk the other one checking hash. (If same number is in there twice you mark it in hash table as number 2 then while walking you substract 1 each time you find that number. When you don't find it in hash, that is the number.

Yes xor will do the work and is faster than adding and hashing

I have a question,tht if the number r not in order how xor will help ..plz give a algo

The problem has two cases:

1. If only 1 element is missing:

Here do the XOR of all the elements and the ans will be the missing one.

2. If more than 1 element are missing:

Use the method of hashing or sort the stack in place and do the comparision.

hi can anyone provide a small example? I did not understand the algorithm, yet.
Thanks

#include "stdio.h"

int main()
{
int stack1[]={10,12,13,14};
int stack2[]={12,10,14};
int size1= sizeof(stack1)/sizeof(stack1[0]);
int size2= sizeof(stack2)/sizeof(stack2[0]);
int missednumb=0;
int i=0;
if (size2<size1)
{
while(i<size2)
{
missednumb^=stack1[i]^stack2[i];
i++;
}

}
else
{
while(i<size1)
{
missednumb^=stack1[i]^stack2[i];
i++;
}
}
if (size2<size1)
{
missednumb^=stack1[i];
}
if (size1<size2)
{
missednumb^=stack2[i];
}
printf("\n The Missed number is %d",missednumb);
return 0;
}

for both stack s1,s2

pop elements of s1 first
-maintain a separate negativesum and a positivesum(sum of negative & positive no.s respectively);
-lets say they r ns1 &  ps1
similarly for s2
find ns2,ps2

now 
if(ns1==ns2) { if(ps2>ps1) missingno=ps2-ps1; 
                        else missingno=ps1-ps2;
                      }
else if(ps1==ps2) { if(ns2>ns1) missingno=ns2-ns1; 
                        else missingno=ns1-ns2;
                      }