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 <[email protected]> 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 <[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. > -- 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 [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.
