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 <[email protected]> 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 <[email protected]>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 <[email protected]>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 >>> <[email protected]>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 <[email protected]>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 < >>>>> [email protected]> 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 <[email protected] >>>>>> > 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 < >>>>>>> [email protected]> 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 <[email protected] >>>>>>>> > 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 < >>>>>>>>> [email protected]> 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 <[email protected]>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 <[email protected]> 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 [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. >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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 [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. >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Varun Pahwa >>>>>>> B.Tech (IT) >>>>>>> 7th Sem. >>>>>>> Indian Institute of Information Technology Allahabad. >>>>>>> Ph : 09793899112 ,08011820777 >>>>>>> Official Email :: [email protected] >>>>>>> Another Email :: [email protected] >>>>>>> >>>>>>> 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 [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. >>>>> >>>> >>>> >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >> > > -- > 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. > -- **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 [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.
