Skip to main content
1 of 6
user avatar
user avatar

Given $N$ integers on a circle , how to choose them in pairs to obtain minimum sum?

$N$ integers $A_1,A_2,A_3....A_N$ are arranged on circle such that $A_i$ is adjacent to $A_{i+1}$ .Also $A_N$ is adjacent to $A_1$. We can choose two adjacent integers (say $A_j,A_{j+1}$) and keep integer with value $A_j+A_{j+1}$ in between them on the circle .Then we can remove $A_j,A_{j+1}$ from the circle. We can keep doing this until one integer is left on circle i.e total $N-1$ times.We need to minimise sum of numbers that were added on the circle by us. Example - $20,10,3$ (in sequence) are arranged on circle.Then first we can choose $10,3$ .Now sequence becomes $20,13$.Then we choose $20,13$ and final sequence becomes $33$. Hence sum of numbers that we added on circle is $13 + 33 = 46$. This is the minimum sum possible. What will be the general procedure to solve this problem ?

user142755