Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.
For example:
Array 1: {1, 2, 4, 5}
Array 2: {4, 8, 16, 125}
Output : 6
The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).
If the array size is $10^5$, an $n^2$ algorithm would be inefficient.
There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x b_x$.
There are many optimizations possible for this general scheme, which in practice can speed it up significantly. I'll let you work them out.
The numbers involved are small, which makes this quite trivial. The numbers are ≤ $10^5$. We have $10^5 < 47^3$, and there are 14 primes < 47.
So for each of the numbers x, y in X, Y, we calculate a 14 bit integer with bit #i set if x, y is divisible by an odd power of the i-th prime, and we also calculate x', y' which are x, y divided by the fourteen primes < 47. The product of x, y is a square if and only if x, y produced the same bit vector, and x'y' is a square.
We split X, Y with x, y replaced by x', y' into up to 16,384 arrays where all the elements have the same bit vector. Let X', Y' be two such subarrays where all original numbers had the same bit vector, and all the numbers have been divided by the primes < 47.
We first handle squares: If x', y' are both squares then the product is a square. If only one of them is a square then the product is not a square. Let X' contain n squares and Y' contain m squares, then we have nm square products, and remove the squares from X', Y'.
Now the elements of X' are all less than $10^5$, all have no prime factors < 47, and none are squares. The smallest number with three prime factors ≥ 47 is $47^3 < 10^5$, therefore each x', y' is either prime or the product of two primes. The product of two such numbers is a square if and only if they are the same, that is x' = y'. We therefore easily find the squares after sorting each array. We need to be a bit careful because each array can contain the same number twice.
All in all, this takes O (n log n) steps, where n is the size of the larger array. If the numbers were less than $10^{15}$ then we'd want to divide them by all primes < 100,000 which would still be O (n log n) but with a much larger constant.
