You will use three properties of XOR on two issues:
A XOR A = 0
A XOR B XOR B = A (commutativity)
A XOR (B XOR C) = (A XOR B) XOR C (Associativity)
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Thu, Jun 9, 2011 at 8:28 AM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
> 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 <duman...@gmail.com> 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 <sunny816.i...@gmail.com> wrote:
>> > yes, but using xor no need of ULL :)
>> >
>> > 2011/6/9 • » νιρυℓ « • <vipulmehta.1...@gmail.com>
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > Sum wont overflow, ULL range will include sum.
>> >
>> > > On Thu, Jun 9, 2011 at 3:52 PM, sunny agrawal <
>> sunny816.i...@gmail.com>wrote:
>> >
>> > >> sum can overflow....
>> > >> Xor method can also be applied to Q1. no need of numbers to be
>> sorted.
>> >
>> > >> 2011/6/9 • » νιρυℓ « • <vipulmehta.1...@gmail.com>
>> >
>> > >>> 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 <
>> navneetn...@gmail.com>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 <duman...@gmail.com>
>> 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 algogeeks@googlegroups.com.
>> > >>>> > To unsubscribe from this group, send email to
>> > >>>> algogeeks+unsubscr...@googlegroups.com.
>> > >>>> > 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 algogeeks@googlegroups.com.
>> > >>>> To unsubscribe from this group, send email to
>> > >>>> algogeeks+unsubscr...@googlegroups.com.
>> > >>>> 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 algogeeks@googlegroups.com.
>> > >>> To unsubscribe from this group, send email to
>> > >>> algogeeks+unsubscr...@googlegroups.com.
>> > >>> 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 algogeeks@googlegroups.com.
>> > >> To unsubscribe from this group, send email to
>> > >> algogeeks+unsubscr...@googlegroups.com.
>> > >> 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 algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
