 # MINSM - Editorial

Author: Ram Gopal Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

1315

None

# PROBLEM:

You have an array of length N. In one move, you can replace 2 elements by their gcd. What is the minimum possible sum of the final array?

# EXPLANATION

Let G = \gcd(A_1, A_2, \ldots, A_N). The answer is simply N \cdot G.

Clearly, it is not possible to make any element less than G because G divides every element of A. Conversely, it is possible to make every element equal to G - to make the i-th element equal to G, perform the operations on (1, i), (2, i), (3, i), \ldots, (N, i).

All that remains is to compute G. This is easy - using the fact that \gcd(a, b, c) = \gcd(a, \gcd(b, c)), we can simply initialize G to A_1, and then run a loop of i from 2 to N, each time doing G \gets \gcd(G, A_i).

# TIME COMPLEXITY:

\mathcal{O}(N + \log M) per test case, where M is the maximum element of the array.

# CODE:

Editorialist's code (Python)
import math
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(n * math.gcd(*a))

1 Like

Can someone tell me what’s wrong with my logic - I thought possible outcome will always be either n or min*n
following is code:
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
long long int n ,min = INT_MAX;
bool flag = false;
cin>>n;
long long int arr[n],temp;
for(int i = 0;i<n;i++){
cin>>arr[i];
if(min>arr[i]){
min = arr[i];
temp = i;
}
}

  for(int i=0;i<n && temp != i;i++){
if(arr[i]%min != 0){
flag = true;
}
}

if(flag == true){
cout<<n<<endl;
}
else{
cout<<min*n<<endl;
}

}
return 0;


}

The answer is not always N or \min \cdot N. For example, consider the test case

1
2
4 6


where the answer is 2\cdot 2 = 4.

Please read the editorial to see the actual solution to the problem.

3 Likes

can someone explain what’s wrong with this

#include<bits/stdc++.h>
using namespace std;

int main(){

int t;
cin >> t;
while(t--){
int n ;
int arr[n];
cin >> n ;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}
int gcd= 0;
for (int i = 0; i < n; ++i){
gcd = __gcd(gcd,arr[i]);
}

cout << gcd*n << endl;

}


}

Overflow?

Declare your array after taking n as input because right now it doesn’t know what n is so it will show runtime error
and
instead of int n take long long n because of the constraints
.
.
.
Hope it helps <3

Yeah thanks … rookie mistake i didn’t even noticed i did that

1 Like

He is taking GCD with zero and the answer will be 0

The greatest common divisor of a positive integer a and 0 will be a since a can divide 0.