Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  muzzlator Mar 18 '13 at 20:42
    
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? –  muzzlator Mar 18 '13 at 20:44
    
Oops! My mistake. Yes it's not the sum. @muzzlator Yes it is indeed what I seek. Thanks! –  Vivek Rai Mar 19 '13 at 4:44

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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