[Solution] Minimum Sum solution codechef

Table of Contents

Minimum Sum solution codechef

Minimum Sum solution codechef – 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.
  • 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.

[Solution] Minimum Sum solution codechef

  • 1 \leq T \leq 100
  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • The sum of N over all test cases won’t exceed 3 * 10^5.

Sample 1:



5 10
2 2 6

[Solution] Minimum Sum solution codechef 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.

For Solution

“Click Here”

Leave a Comment