PROBLEM LINK:
Author: Sahil Tiwari
Tester: Aman Singhal
Editorialist: Satyam Garg
DIFFICULTY:
EASY
PREREQUISITES:
Math, GCD, Euclidean Algorithm
PROBLEM:
Given an array A with N elements, you want to calculate the minimum possible value of A_1 + A_2 + \ldots + A_N, by performing these operations several (possibly, 0) times. In one operation you can  Select any two indexes 1 \leq i, j \leq N such that i \neq j and replace A_i with A_i  A_j.
QUICK EXPLANATION:

Using the result of the Euclidean Algorithm for GCD  If you subtract a smaller number from a larger one, GCD doesnâ€™t change and if we keep subtracting repeatedly the larger of two, we end up with GCD.

Since the array might contain positive as well as negative numbers, we need to take account of the following cases: an array containing only one positive and one negative number, only nonnegative numbers, only nonpositive numbers, and a combination of positive and negative integers.
EXPLANATION:
First of all, we should keep in mind that our ultimate goal is to bring all the elements of the array as closer to 0 as possible to minimize the value of A_1 + A_2 + \ldots + A_N.
Having said that, let us take a closer look at the only operation we are allowed to use in order to modify array elements. According to the problem, we have to Select any two indexes 1 \leq i, j \leq N such that i \neq j and replace A_i with A_i  A_j.
Consider two array elements X and Y. Now, if we keep on subtracting the smaller number from the greater one, one of the numbers will become zero and the other one will have a value equal to GCD(X, Y).
Basic Idea:
Let us consider two positive numbers X and Y and WLOG let us assume that X>=Y. Also, let us consider that GCD(X,Y) = F.
It means that F divides both and X and Y. So, we can write X = C*F and Y = D*F. Let us replace X with XY.
X = X  Y
X = C*F  D*F
X = F*(CD)
Now, clearly GCD((XY),Y) = GCD((F*(CD), DF) = F. Therefore, using this result repeatedly, we will obtain two numbers, GCD(X, Y) and 0. This can also be proved using Euclidean Algorithm for GCD.
Now that we have understood that how we will reduce two numbers of the same parity, we can separately calculate the gcd of positive and negative numbers. Meanwhile, we must maintain the count of positive, negative, and zero numbers.
The problem reduces to four further cases:
Case 1: All numbers are nonnegative
In this case, we will simply print the GCD of positive numbers.
Case 2: All numbers are nonpositive
In this case, we will simply print the GCD of negative numbers.
Case 3: The array contains only one positive and one negative number.
In this case, we cannot reduce the summation of the absolute value of respective elements as the given operation would only result in increasing the value of absolute of the number.
Case 4: All possibilities except mentioned above
Now, when we address any general array of numbers, there comes a nonintuitive case.
Example: A = [4,0,3]
At first glance, this will appear similar to case 3. But, if we think carefully, we can change 0 to (04) = 4, and then after applying the Euclidean algorithm for gcd, we can reduce [4,3] to [1,0]. Again this 0 can be changed to 0  (1) = 1, and applying the Euclidean algorithm on [4,1] repeatedly, we will achieve [1,0]. Therefore the minimum value of the expression will be 2.
We can similarly extend this example to any array except the ones mentioned in the 3 cases given above.
Therefore, the answer will be 2*(GCD(GCD of positive numbers, GCD of negative numbers)).
Time Complexity:
The time complexity is O(N*log( Max element of Array A )) per test case.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
if (b > a)
swap(a, b);
if (b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
int t;
cin >> t;
while (t)
{
int n;
cin >> n;
vector<int> pos, neg;
int x, z = 0;
while (n)
{
cin >> x;
if (x > 0)
pos.push_back(x);
else if (x < 0)
neg.push_back(x);
else
z++;
}
int a = 0, b = 0;
for (int i : pos)
a = gcd(a, i);
for (int i : neg)
b = gcd(b, i);
if (pos.size() == 1 && neg.size() == 1 && z == 0)
{
cout << a + b << endl;
}
else if (pos.size() == 0  neg.size() == 0)
{
cout << a + b << endl;
}
else
{
cout << 2 * gcd(a, b) << endl;
}
}
return 0;
}
Tester's Solution
from math import gcd
T=int(input())
for _ in range(T):
N=int(input())
A=list(map(int,input().split()))
cntp=0
cntn=0
ans=abs(A[0])
for i in range(N):
ans=gcd(ans,abs(A[i]))
if (A[i]>0):
cntp+=1
elif(A[i]<0):
cntn+=1
if (cntp==0 or cntn==0):
print(ans)
elif (cntp==cntn==1 and N==2):
print(abs(A[0])+abs(A[1]))
else:
print(2*ans)
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int t;
cin >> t;
while (t) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int pos_gcd = 0, neg_gcd = 0;
int pos_count = 0, neg_count = 0, z_count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
z_count++;
}
else if (arr[i] < 0) {
neg_gcd = gcd(neg_gcd, abs(arr[i]));
neg_count++;
}
else {
pos_gcd = gcd(pos_gcd, arr[i]);
pos_count++;
}
}
if (z_count == 0 && pos_count == 1 && neg_count == 1) {
cout << arr[0] + arr[1] << "\n";
}
else if (pos_count == 0) {
cout << neg_gcd << "\n";
}
else if (neg_count == 0) {
cout << pos_gcd << "\n";
}
else {
cout << 2 * (gcd(neg_gcd, pos_gcd)) << "\n";
}
}
return 0;
}