@Saikat: Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Usually, it takes 2N equations to determine 2N unknowns, although other information about the solutions can lessen that number in certain circumstances.
At least if you are going to propose something, do so only after you have tested it on all of the combinations of up to four numbers between -5 and 5. Dave On Aug 19, 11:52 am, Saikat Debnath <[email protected]> wrote: > 1. Add sum of squares of all numbers in respective groups, if equal > goto step 2. > 2. XOR all elements of both groups, (if==0) elements are same. > > On Aug 19, 9:21 pm, Dave <[email protected]> wrote: > > > > > @Nikhil Jindal: What you say is true for 2 numbers, but not for more > > than 2. > > 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. > > > Dave > > > On Aug 19, 6:00 am, Nikhil Jindal <[email protected]> wrote: > > > > Nikhil's algo is correct if the following is always true: > > > > Given: x + y = S, x * y = M > > > and x' + y' = S', x' * y' = M' > > > > If: S' = S and M' = M, then x = x' and y = y' > > > i.e for given sum and product, the elements are unique. > > > > On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal > > > <[email protected]>wrote: > > > > > @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . > > > > > S1=0;S2=0; > > > > M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) > > > > M1!=M2 there fore it is correct. > > > > > Code: > > > > > bool check_arrays(vector<int> v1,vector<int> v2){ > > > > if(v1.size()!=v2.size()) > > > > return 0; > > > > if(v1.size()==0&&v2.size()==0) > > > > return 1; > > > > int sum,product1,product2; > > > > sum=0;product1=1;product2=1; > > > > for(int i=0;i<v1.size();i++){ > > > > sum+=v1[i]; > > > > sum-=v2[i]; > > > > if(v1[i]!=0) > > > > product1*=v1[i]; > > > > if(v2[i]!=0) > > > > product2*=v2[i]; > > > > } > > > > if(sum==0&&(product1==product2)) > > > > return 1; > > > > return 0; > > > > } > > > > On Thu, Aug 19, 2010 at 11:26 AM, Dave <[email protected]> wrote: > > > > >> @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B > > > >> = > > > >> (0,2,-3). I was thinking ones-complement arithmetic instead of twos- > > > >> complement. > > > > >> Dave > > > > >> On Aug 18, 11:59 pm, Dave <[email protected]> wrote: > > > >> > @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = > > > >> > (0,2,-2). > > > > >> > Dave > > > > >> > On Aug 18, 10:53 pm, srinivas reddy <[email protected]> wrote: > > > > >> > > add one more thing to the solution suggested by nikhil i.e;count > > > >> > > the > > > >> number > > > >> > > of elements in array 1 and number of elements in array2 if these > > > >> > > two > > > >> values > > > >> > > are equal then after follow the algo proposed by nikhil agarwal.. > > > > >> > > On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan > > > >> > > <[email protected]> > > > >> wrote: > > > >> > > > @Chonku: Your algo seems to fail with following input. > > > >> > > > Arr1[]= {1,6} > > > >> > > > Arr2[]={7} > > > > >> > > > On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan > > > >> > > > <[email protected] > > > >> >wrote: > > > > >> > > >> @Nikhil: Your algo seems to fail with following input. What do > > > >> > > >> you > > > >> say? > > > >> > > >> Arr1[]= {1,2,3} > > > >> > > >> Arr2[]={6} > > > > >> > > >> On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal < > > > >> > > >> [email protected]> wrote: > > > > >> > > >>> Sum all the elements of both the arrays..let it be s1 and s2 > > > >> > > >>> Multiply the elements and call as m1 and m2 > > > >> > > >>> if(s1==s2) &&(m1==m2) > > > >> > > >>> return 1;else > > > >> > > >>> return 0; > > > > >> > > >>> O(n) > > > > >> > > >>> On Tue, Aug 17, 2010 at 11:33 PM, amit > > > >> > > >>> <[email protected]> > > > >> wrote: > > > > >> > > >>>> Given two arrays of numbers, find if each of the two arrays > > > >> > > >>>> have > > > >> the > > > >> > > >>>> same set of integers ? 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]<algogeeks%2bunsubscr...@googlegroups > > > >> > > >>>> .com> > > > >> <algogeeks%2bunsubscr...@googlegroups.com> > > > >> > > >>>> . > > > >> > > >>>> For more options, visit this group at > > > >> > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > > >> > > >>> -- > > > >> > > >>> Thanks & Regards > > > >> > > >>> Nikhil Agarwal > > > >> > > >>> Senior Undergraduate > > > >> > > >>> Computer Science & Engineering, > > > >> > > >>> National Institute Of Technology, Durgapur,India > > > >> > > >>>http://tech-nikk.blogspot.com > > > >> > > >>>http://beta.freshersworld.com/communities/nitd > > > > >> > > >>> -- > > > >> > > >>> 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]<algogeeks%2bunsubscr...@googlegroups > > > >> > > >>> .com> > > > >> <algogeeks%2bunsubscr...@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 [email protected]. > > > >> > > > To unsubscribe from this group, send email to > > > >> > > > [email protected]<algogeeks%2bunsubscr...@googlegroups > > > >> > > > .com> > > > >> <algogeeks%2bunsubscr...@googlegroups.com> > > > >> > > > . > > > >> > > > For more options, visit this group at > > > >> > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext- > > > > >> > > - Show quoted text -- Hide quoted text - > > > > >> > - Show quoted text - > > > > >> -- > > > >> 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]<algogeeks%2bunsubscr...@googlegroups > > > >> .com> > > > >> . > > > >> For more options, visit this group at > > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > > Thanks & Regards > > > > Nikhil Agarwal > > > > Senior Undergraduate > > > > Computer Science & Engineering, > > > > National Institute Of Technology, Durgapur,India > > > >http://tech-nikk.blogspot.com > > > >http://beta.freshersworld.com/communities/nitd > > > > > -- > > > > 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]<algogeeks%2bunsubscr...@googlegroups > > > > .com> > > > > . > > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > Please access the attached hyperlink for an important electronic > > > communications > > > disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php-Hidequoted > > > text - > > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- 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.
