Suppose you are given an array A of n distinct integers as an input and the goal is to compute the number of pairs of indices $($i$,$ j$)$ such that A$[$i$]=$ A$[$j$]2.$

For example, consider the following array: A $=[2,4,9,16,3].$

This array has $3$ pairs: $(2,4),(3,9)$ and $(4,16).$ So the algorithm should return $3.$

$($a$)$ The brute$-$force solution to this problem would be to test every possible pair. Write an algorithm in python which implements this approach and describe its run time.

$($b$)$ Would sorting the array first help in solving the problem faster? I claim the answer is yes. Write an algorithm which first sorts the array using either quicksort or mergesort, and then determines the number of pairs in linear time. $($So that the overall runtime is O$($n log$($n$))+$ O$($n$)=$ O$($n log$($n$)).)$