Could anyone help me with the code of this exercise? | Sololearn: Learn to code for FREE!

0

Could anyone help me with the code of this exercise?

Given two arrays a and b write a function comp(a,b) that checks whether the two arrays have the “same” elements, with the same multiplicities. “Same” means, here, that the elements in b are the elements in a squared, regardless of the order.

5/22/2017 3:08:04 PM

Sebastián Abarca

1 Answer

New Answer

0

Hello :> Offhand I can think of two possible solutions: 1) simply iterating through all the elements in a. for each element in a, you search the whole array b to check if a^2 is in b. time taken: O(n^2) 2) sort the elements in array b first, then conduct binary search for a^2 each time. time taken: O(n log n + n log n) = O(n log n)