[Solution] Minimum Sum CodeChef Solution

Problem

You are given an array $A_1, A_2, \dots, A_N$ of length $N$. You can perform the following operation any number of times (possibly 0 times) :

• Choose two distinct indices $i$ and $j$ and replace either $A_i$ or $A_j$ with $\gcd(A_i,A_j)$.

Find the minimum possible sum (ie. $A_1 + A_2 + \dots + A_N$) that you can achieve, and output that.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• The first line of each test case contains an integer $N$ - the length of the array $A$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• The second line of each test case contains $N$ space-separated integers $A_1,A_2,\ldots,A_N$.​

Output Format

For each test case, output on a new line the minimum sum of the array that can be achieved.

Explanation:

Test case $1$: Choose $i=1,j=2$ and replace $A_2$ with $\gcd(5,10)=5$.

Test case $2$: Choose $i=1,j=3$ and replace $A_3$ with $\gcd(2,6)=2$.