I guess this question is similar to anagram.
On Mon, Jul 4, 2011 at 1:07 AM, Arpit Sood <soodfi...@gmail.com> wrote:
> Hey,
> what is the solution with XOR,,,,,,,,,,,,, methods mentioned above seem to
> fail there.... any reference ?
>
>
> On Sun, Jul 3, 2011 at 10:39 PM, Deoki Nandan <deok...@gmail.com> wrote:
>
>> there is no possible solution for this question in less than O(nlgn) time.
>> As by theorem given in cormen and solution is possible using xor
>>
>>
>> On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain <sandeep6...@gmail.com>wrote:
>>
>>> For case1) yes XOR works,
>>> for Well, for the other two cases hash-maps may come in handy. :)
>>>
>>>
>>> Regards,
>>> Sandeep Jain
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal
>>> <sunny816.i...@gmail.com>wrote:
>>>
>>>> But i don't think xor method will work at all for all of the cases above
>>>> you mentioned.
>>>> setA = {4,7}
>>>> setB = {5,6}
>>>>
>>>> -> all numbers in both set are nonzero and distinct
>>>> -> all numbers are in some range :D
>>>> and for character parts it will similarly fail....by taking character
>>>> set of ascii values 4,5,6,7
>>>>
>>>> and about general solution i dont know how to do it in O(n)
>>>> one thing i was thinking of goes this way, taking arrays A and B instead
>>>> of sets.
>>>> if we can prove these polynomial to be same in O(n) time.
>>>> (x-a[0])*(x-a[1])*.................*(x-a[n-1]) ==
>>>> (x-b[0])*(x-b[1])*.........(x-b[n-1])
>>>> dont know if it can be done efficienty
>>>>
>>>>
>>>> On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain <sandeep6...@gmail.com>wrote:
>>>>
>>>>> Agreed, BUT if you don't add a stipulation. You won't be able to reduce
>>>>> the complexity.
>>>>> For a 100% general solution, I don't think you can reduce the
>>>>> complexity more than O(nLgn.)
>>>>> There are variations of this question:
>>>>> --> All numbers are non-zero and distinct.
>>>>> --> All numbers belong to given range
>>>>> --> You can also have character's in place of numbers
>>>>> In all the above cases, you will have time complexity O(n)
>>>>>
>>>>> PS: I'm definitely looking forward to learn a solution, better than
>>>>> O(nLgn)
>>>>>
>>>>>
>>>>>
>>>>> Regards,
>>>>> Sandeep Jain
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal <sunny816.i...@gmail.com
>>>>> > wrote:
>>>>>
>>>>>> @sandeep
>>>>>> SET A -> {0,3,4,7}
>>>>>> SET B -> {1,2,5,6}
>>>>>>
>>>>>> xor of all elements is zero
>>>>>> sum of both the sets is same
>>>>>> no of elements in both are same
>>>>>>
>>>>>> overall result : all Algorithm posted above Fails
>>>>>>
>>>>>> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain
>>>>>> <sandeep6...@gmail.com>wrote:
>>>>>>
>>>>>>> I was thinking the same, BUT here the question is that we have two
>>>>>>> *SETS* and that's the catch.
>>>>>>> So, XORing all elements of SET A with SET B should result in ZERO
>>>>>>> only when both the set have same elements.
>>>>>>>
>>>>>>>
>>>>>>> Regards,
>>>>>>> Sandeep Jain
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
>>>>>>> meetpranav...@gmail.com> wrote:
>>>>>>>
>>>>>>>> I think that the above algo will fail for the following two arrays:
>>>>>>>> a={2,2,3,3}
>>>>>>>> b={4,4,1,1}
>>>>>>>>
>>>>>>>> sum(a)=sum(b);
>>>>>>>> a^b=0;
>>>>>>>> len(a)=len(b);
>>>>>>>>
>>>>>>>> Correct me if i am wrong!
>>>>>>>>
>>>>>>>> Pranav
>>>>>>>>
>>>>>>>>
>>>>>>>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa <
>>>>>>>> varunpahwa2...@gmail.com> wrote:
>>>>>>>>
>>>>>>>>> @aditya. xor all elements mean that. take xor of each element of
>>>>>>>>> 1st array store in a variable that take xor of variable and each
>>>>>>>>> element of
>>>>>>>>> the second array if all elements are common then the variable will be
>>>>>>>>> 0 some
>>>>>>>>> where.
>>>>>>>>> var = a[0];
>>>>>>>>> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
>>>>>>>>> var = var ^ a[i];
>>>>>>>>> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
>>>>>>>>> var = var ^ b[i];
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
>>>>>>>>> aditya.kumar130...@gmail.com> wrote:
>>>>>>>>>
>>>>>>>>>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i
>>>>>>>>>> dont think dat you can find second largest in less than O(n).
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal <
>>>>>>>>>> mohitm.1...@gmail.com> wrote:
>>>>>>>>>>
>>>>>>>>>>> Dont think that the corresponding elements should be same.
>>>>>>>>>>> XOR Should do it anyway.
>>>>>>>>>>>
>>>>>>>>>>> Btw other question "How would you find the second largest
>>>>>>>>>>> element in an array using minimum no of comparisons?Any thing
>>>>>>>>>>> better than
>>>>>>>>>>> O(n)."?
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>>>>>>>>>>> aditya.kumar130...@gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> xor will only result if corresponding elements are same . what
>>>>>>>>>>>> if in both the array set of integers are same but they arnt
>>>>>>>>>>>> corresponding to
>>>>>>>>>>>> each other ??
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu <duman...@gmail.com>wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>> xor all the elements of both arrays ==0
>>>>>>>>>>>>> sum of 1st array == sum of 2nd array
>>>>>>>>>>>>> no. of elements in 1st == no. of elements in 2nd
>>>>>>>>>>>>> if the above conditions are met, they have the same set.
>>>>>>>>>>>>> m i missin sth?
>>>>>>>>>>>>> On Jul 3, 1:23 am, mittal <mohitm.1...@gmail.com> wrote:
>>>>>>>>>>>>> > Given two arrays of numbers, find if each of the two arrays
>>>>>>>>>>>>> have the same
>>>>>>>>>>>>> > set of ntegers ? Suggest an algo which can run faster than
>>>>>>>>>>>>> NlogN without
>>>>>>>>>>>>> > extra space?
>>>>>>>>>>>>>
>>>>>>>>>>>>> --
>>>>>>>>>>>>> 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.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> Mohit Mittal
>>>>>>>>>>> 4th year , Computer Engineering
>>>>>>>>>>> Student-Coordinator , DTU WebTeam
>>>>>>>>>>> Delhi Technological University
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> 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.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> Varun Pahwa
>>>>>>>>> B.Tech (IT)
>>>>>>>>> 7th Sem.
>>>>>>>>> Indian Institute of Information Technology Allahabad.
>>>>>>>>> Ph : 09793899112 ,08011820777
>>>>>>>>> Official Email :: rit2008...@iiita.ac.in
>>>>>>>>> Another Email :: varunpahwa.ii...@gmail.com
>>>>>>>>>
>>>>>>>>> People who fail to plan are those who plan to fail.
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>>
>>>>>
>>>>> --
>>>>> 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.
>>>>
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> **With Regards
>> Deoki Nandan Vishwakarma
>>
>> *
>> *
>>
>> --
>> 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,
> Arpit Sood
>
> --
> 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.
