# MSUM - Editorial

Practice

Author: Sahil Tiwari

Tester: Aman Singhal

Editorialist: Satyam Garg

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 non-negative numbers, only non-positive 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 X-Y.

X = X - Y

X = C*F - D*F

X = F*(C-D)
Now, clearly GCD((X-Y),Y) = GCD((F*(C-D), 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 non-negative

In this case, we will simply print the GCD of positive numbers.

Case 2: All numbers are non-positive

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 non-intuitive 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 (0-4) = -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;
}

2 Likes

Hi!!
I have tried to solve this problem from practice section about 10 times, but still I am getting wrong answer; I am not able to understand where is my solution approach failing. It will be highly appreciated if anybody can help with the same, as of which where are my test cases failing.

Below is my code for this MSUM problem:::

#include<bits/stdc++.h>
#include
#include
using namespace std;
#define ll long long int
#define pb push_back

int getGCD(vectorv){
if(v.size()==0) return 0LL;
if(v.size()==1) return v[0];
ll gcd=v[0];
for(int i=1; i<v.size();i++) gcd=__gcd(v[i],v[i-1]);
return gcd;
}

void solve(){
int n;
cin>>n;
vectorarr(n),pos,neg;
for(int i=0; i<n;i++) cin>>arr[i];
for(int i=0; i<n;i++){
if(arr[i]>0)(pos.pb(arr[i]));
if(arr[i]<0)(neg.pb(-arr[i]));
}
int gcdpos=getGCD(pos);
int gcdneg=getGCD(neg);

if(n==2 && pos.size()==1 && neg.size()==1){
cout<<pos[0]+neg[0]<<endl;
return;
}
else if(pos.size()==0 || neg.size()==0){
cout<<(gcdpos+gcdneg)<<endl;
return;
}
else{
cout<<2*(__gcd(gcdpos,gcdneg))<<endl;
return;
}}

int main(){
#ifndef ONLINE_JUDGE
freopen(“inputx.txt”,“r”,stdin);
freopen(“outputx.txt”,“w”,stdout);
#endif
int t;
cin>>t;
while(t–){
solve();
}}

getGCD function is wrong.

Hey there!! Thanks for ur much appreciated help.
But bro I am still not getting where my getgcd function is wrong. Can u plz elaborate on the same?!

It should be
gcd=__gcd(v[i],gcd);