1st of all "Happy New Year to All" :) Must be both have same length also test some other test cases, :)
Let me share things striking in mind , if you calculate the sum of power of 1st array by taking any number as base , remaining all the numbers as exponent so if take 3 as base & calculate the for i =0 to n sum1+=3^a[i]; whats the complexity it will be O(nlogn) , becoz pow(a,b) can be done in O(logb) we doing for n number so why its O(nlogn) Now sort the 2nd array O(mlogm) , find the number which we have taken as base in 1st array , it will take O(logm) binary search now calculate the sum of all the remaining elements with base we found (base has to be same) as 2nd array has 3 , we found base as 3 here as well. for j=0 to m sum2+=3^b[j] finally compare sum1==sum2 ??? approach may be sounds naive , but think over complexity O(nogn) + O(mlogm) where m=n , we are not using any extra space as well . some of you may wondering why it will work , try to find out simple math behind it . Let me know if anything wrong or missed something ? comments are welcome :) Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fg4qEJf3v_AJ. 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.
