Suppose I have an array of elements A[n]. I wish to minimize the square root of pairwise product expression sqrt(m1*m2) , where m1 and m2 are the two elements of the array. (It is rounded off to lower integer)

for example, A[3] = {72,35,50,30} , the answer would be 125.

Please suggest the algorithm or the possible pseudo code for this. Thanks!

EDIT (for more clarity) : I guess I was a little unclear in the question. We first multiply two numbers, then replace it in the array with remaining. Then again carry out this product (with the rest of the numbers) and keep on doing so until there is only a single number which is minimum of all possible ways.

  • $\begingroup$ Are you asking how to arrange the elements initially so that $\sqrt{m_n \dots \sqrt{m_3 \sqrt{m_1 m_2}}}$ is minimised? $\endgroup$ – muzzlator Mar 18 '13 at 20:42
  • $\begingroup$ Also, you refer to a "sum" in the question. Do you actually mean the product? And are your numbers always going to be positive integers? $\endgroup$ – muzzlator Mar 18 '13 at 20:44
  • $\begingroup$ Oops! My mistake. Yes it's not the sum. @muzzlator Yes it is indeed what I seek. Thanks! $\endgroup$ – Vivek Rai Mar 19 '13 at 4:44

Assuming you have $n$ distinct positive integers $m_1, \dots m_n$ and you are trying to find a permutation $\sigma \in S_n$ (a reordering) such that the quantity

$$ P = \sqrt{m_{\sigma n} \dots \sqrt{m_{\sigma 3} \sqrt{m_{\sigma 2} m_{\sigma1}}}} $$

is minimized.

You want the largest number to be square rooted the most times so sort the array in descending order. To see why this is more clearly, consider $P^{2^n}$ and notice that it's always better to put the higher powers over smaller numbers to minimise the quantity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.