MINSM - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

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

DIFFICULTY:

1315

PREREQUISITES:

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?

Video Solution :

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.