Xoring it twice ...once with the elements in the file and then from i=1 to 4,000,000,000..the answer left is the missing number
On Thu, Jun 9, 2011 at 4:46 PM, Dumanshu <[email protected]> wrote: > I dont think numbers are sorted in the 1st question. btw > @sunny: how will xor-ing give the ans? for 1st ques? > > On Jun 9, 3:34 pm, sunny agrawal <[email protected]> wrote: > > yes, but using xor no need of ULL :) > > > > 2011/6/9 • » νιρυℓ « • <[email protected]> > > > > > > > > > > > > > > > > > > > > > Sum wont overflow, ULL range will include sum. > > > > > On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal <[email protected] > >wrote: > > > > >> sum can overflow.... > > >> Xor method can also be applied to Q1. no need of numbers to be sorted. > > > > >> 2011/6/9 • » νιρυℓ « • <[email protected]> > > > > >>> For 1. > > >>> sum the numbers in the file, subtract it from sum of first 4 billion > > >>> numbers. > > > > >>> On Thu, Jun 9, 2011 at 3:44 PM, Navneet Gupta <[email protected] > >wrote: > > > > >>>> The answer to second question is simple. XORing all the elements > > >>>> should do it for you. > > > > >>>> On Thu, Jun 9, 2011 at 3:15 PM, Dumanshu <[email protected]> > wrote: > > >>>> > Q1. I have a file in which there are supposed to be 4 billion > > >>>> > numbers, > > >>>> > starting from 1 to 4,000,000,000 but unfortunately one number is > > >>>> > missing, > > >>>> > i.e there are only 3,999,999,999 numbers, I need to find the > missing > > >>>> > number. > > > > >>>> > Q2. I have an array consisting of 2n+1 elements. n elements in it > are > > >>>> > married, i.e they occur twice in the array, however there is one > > >>>> > element > > >>>> > which only appears once in the array. I need to find that number > in a > > >>>> > single pass using constant memory. {assume all are positive > numbers} > > >>>> > Eg :- 3 4 1 3 1 7 2 2 4 > > >>>> > Ans:- 7 > > > > >>>> > -- > > >>>> > You received this message because you are subscribed to the Google > > >>>> Groups "Algorithm Geeks" group. > > >>>> > To post to this group, send email to [email protected]. > > >>>> > To unsubscribe from this group, send email to > > >>>> [email protected]. > > >>>> > For more options, visit this group at > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > > >>>> -- > > >>>> --Navneet > > > > >>>> -- > > >>>> You received this message because you are subscribed to the Google > > >>>> Groups "Algorithm Geeks" group. > > >>>> To post to this group, send email to [email protected]. > > >>>> To unsubscribe from this group, send email to > > >>>> [email protected]. > > >>>> For more options, visit this group at > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > > >>> -- > > >>> Regards, > > >>> Vipul > > > > >>> -- > > >>> You received this message because you are subscribed to the Google > Groups > > >>> "Algorithm Geeks" group. > > >>> To post to this group, send email to [email protected]. > > >>> To unsubscribe from this group, send email to > > >>> [email protected]. > > >>> For more options, visit this group at > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > > >> -- > > >> Sunny Aggrawal > > >> B-Tech IV year,CSI > > >> Indian Institute Of Technology,Roorkee > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > Regards, > > > Vipul > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > Sunny Aggrawal > > B-Tech IV year,CSI > > Indian Institute Of Technology,Roorkee > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=100000655377926 * -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
