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 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;
}
… thnxss a lot brother !!