SEAARASU - Editorial

PROBLEM LINK

Practice
Contest

Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Contest Admin: Praveen Dhinwa
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

DIFFICULTY:

Easy

PREREQUISITES:

Number Theory, Greatest Common Divisor \left(\gcd\right), Maths

PROBLEM:

Given an array A consisting of N positive integers. In an operation, you will choose two indices i and j, such that A_i \gt A_j and then subtract number A_j from number A_i. Find the minimum possible sum of the array after applying above operation any number of times.

QUICK EXPLANATION

It is easy to notice that after applying all the operations, all the values in the given array will be equal otherwise we can still choose a pair of indices i and j such that A_i \gt A_j and can reduce the sum further. Value of each element after applying all the operation will be equal to Z.

where

Z = \gcd_{{1 \le i \le N }}(A_i)

Therefore, minimum possible sum will be equal to N * Z.

EXPLANATION

Lets solve this problem for some smaller cases.

Example 1: N = 2 where A_0 = 5 and A_1 = 15.

After 1^{st} operation, A_0 = 5, A_1 = 10.

After 2^{nd} operation, A_0 = 5, A_1 = 5.

NOTE A_0 = A_1 = 5 and we cannot make any further reductions.

Example 2: N = 2 where A_0 = 7 and A_1 = 3.

After 1^{st} operation, A_0 = 4, A_1 = 3.

After 2^{nd} operation, A_0 = 1, A_1 = 3.

After 3^{rd} operation, A_0 = 1, A_1 = 2.

After 4^{th} operation, A_0 = 1, A_1 = 1.

NOTE A_0 = A_1 = 1 and we cannot make any further reductions.

Lets generalise the case for 2 elements say for a and b. Let us consider that the function F_{(a, b)} denotes the minimum equal value that we can achieved by applying given operation
on a and b any number of times.

Function F can be written as:

F_{(a,a)} = a
F_{(a,b)} = F_{(a,b-a)} if(b > a)
F_{(a,b)} = F_{(a-b,b)} if(a > b)

This is actually Greatest Common Divisor (GCD) Function.

For 3 elements a, b, and c. Function F can be written as:

F_{(a,a,a)} = a
F_{(a,b,c)} = F_{(a,b-a,c)} if(b > a)
F_{(a,b,c)} = F_{(a-b,b,c)} if(a > b)
F_{(a,b,c)} = F_{(a,b,c-a)} if(c > a)
F_{(a,b,c)} = F_{(a-c,b,c)} if(a > c)
F_{(a,b,c)} = F_{(a,b-c,c)} if(b > c)
F_{(a,b,c)} = F_{(a,b,c-b)} if(c > b)

which is equivalent to the \gcd(a,b,c).

Associative Property:

\gcd(a,b,c) = \gcd(a,\gcd(b,c))

Euclid Greatest_common_divisor Algorithm:

\gcd(a,0) = a
\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b),

Euclidean GCD C ++ code:

// Euclidean GCD Algorithm
int gcd(int a, int b) {
    if(b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

or inbuilt __gcd() function available in C ++.

Solution code:

int A[N+1];
long long int Z = A[1];
for(int i=2; i<=N; i++) {
  Z = __gcd(ans, A[i]);
}
Z = Z * N; // final answer 
// be careful for the overflow use long long int

COMPLEXITY

O(N\log(\max(A_i)))

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

SIMILAR PROBLEM

Codechef November Long Challenge

Codechef September Cook Off 2013

4 Likes

Where you wrote:

Distributive Property: gcd(a,b,c) = gcd(a,gcd(b,c))

Isn’t that supposed to be Associative Property?

1 Like

This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better.

@bodmas
Thanks
corrected !!!

Please rejudge the problem with stronger test cases.I stress tested a solution and it gives wrong answer on multiple cases.
Solution Link : https://www.codechef.com/viewsolution/8818267
On input :
3
7 11 19
The answer should be 3 but it gives answer as 12.
Still the verdict is Accepted.

1 Like

@shikharid your code is working fine and the answer should be 4 not 3 and your code is also printing 4.