How to combine elements of three arrays to get the wanted result

Question

I was asked this question in an interview:

Given three arrays of unequal sizes and a particular number, I have to select one number from each of the three arrays, and, by dividing the numbers from array1 and array2 and multiplying it with division of numbers from array2 and array3, find whether the a particular number can be obtained or not?

For example: If I have three arrays: 
Array1: 4
Array2: 3 6
Array3: 2 3 8

And I have to find if the number (1/4) can be obtained or not? Yes, it can be since if I select 4 from first array, and 6 from second, and then, 3 from second array and 8 from third array, I can have,

(4/6)*(3/8) which makes it as 1/4. 

How to proceed with this question? I couldn't come up with anything solid for this. Thanks!

Answer 1

Let M be your desired number.

You can go through all pairs (i,j) from (array2,array3) (there are O(n2*n3) of those), and store the value array2[i]/array3[j] in a set.

Then, iterate over all pairs k,l in array1, array2 (there are O(n1*n2) of those), and check if there is a value in the set x such that array1[k]/array2[l] * x = M.
This can be done by simply checking if the value x = M*array2[l] / array1[k] exists in the table.

Assuming balanced tree implementation for the set, this will take O(log(n2*n3) * (n1*n2 + n2*n3)) time.

It can be improved a bit for unequal size arrays by choosing to store array that minimizes the summation of products: x1*x2 + x3*x4 (where x1,x2,x3,x4) are the sizes of arrays, array2 "gets" two variables in this equation), so you can basically have the following "store" combinations:

• array2/array3 (as in the example above)
• array1/array2 (and check for x=M*array3/array2)
• array2/array2 (and check for x=M*array3/array1)
• array1/array3 (and check for x=M*array2/array2)
• array1*array2 (and check for x=M*array3*array2
• 1/(array2*array3) (and check for x=M/(array2*array1)