You can use the same idea:
Suppose you want to find out what the missing number in the list [1 .. 5]:
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
XOR = 001
If the number 4 is missing:
XOR = 001
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
3 = 011
XOR = 011
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Thu, Jun 9, 2011 at 8:34 AM, Ashim Kapoor <[email protected]> wrote:
> Could someone illustrate the XOR for question 2. I am a beginner to this.
>
> Many thanks!
>
>
> On Thu, Jun 9, 2011 at 4:58 PM, Piyush Sinha <[email protected]>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 <[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.
>>
>
> --
> 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.
>
--
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.
