Hi
But does this work on bigger numbers ?
I mean with [11-15] say 14 is missing.
It is:
1011
1100
1101
1111
--------
0101
-------
which is 5 ?
Supraja J
On Sat, Jun 11, 2011 at 8:14 AM, Wladimir Tavares <wladimir...@gmail.com>wrote:
> 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 <ashimkap...@gmail.com>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 <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.
>>
>
> --
> 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.
>
--
U
--
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.
