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.
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)
