What about this approach: First we will scan the first array and find the smallest number. if it is -ve then we increment all numbers in both the arrays by that number . This ensures that every integer in first array is >= 0 some integers in 2nd one maybe -ve if it is,then two arrays are not similar else we follow frequency based tests to find out if two array are similar or not.
Time and space Complexity = O(n) This approach assumes that even after adding that most negative number each number in both arrays will be inside the limits of their data types (long long etc) Any counter test case(s)? On Jan 5, 5:35 pm, saurabh singh <saurab...@gmail.com> wrote: > Some very nice approaches have been presented but I still feels for > practical situations its better to sort and compare......All other > algorithms presented above restricts the max value for an element in the > array.In case the maximum value is small,we can simply count sort,and the > algorithm will still be O(N) (Much simpler and immune to problems such as > finite word size) > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com > > > > > > > > On Thu, Jan 5, 2012 at 5:17 PM, atul anand <atul.87fri...@gmail.com> wrote: > > @Shashank : as i have mentioned in the question , no sorting allowed. > > if question would have allowed sorting then why not sort both array and > > compare it would be much simpler and no need of doing costlier operation > > like finding power. > > > complexity = O(nogn) + O(mlogm) + O(n) > > > -- > > 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.
