My thought process was slightly different, first I observed and verified that the largest and 2nd largest number in the input array can never be together. If we put the largest and 2nd largest number in the same bracket we will never be able to achieve max. sum.
I started by removing the repetitions and sorted, if there’s only single element (call it x) then print 2x.
{GCD(8,8) = 8, GCD of two same numbers is always that number}
If you get two distinct numbers then simply add them and print the result. Since we have sorted the array we will get something like this {a, b, c, d, e, f} all in ascending order.
GCD(a, b, c, d) <= a and GCD(e,f) <= e (case 1 where we’ve taken max and 2nd max together)
GCD(a, b, c, d, e) <= a and GCD(f) == f (case 2)
Now just by looking at the equations we can say that putting max and 2nd max in same bracket is not optimal.
if we just assume that case 1 produces max. results (i.e. a+e, note : when GCD(e,f) == e then f=ne where n!=1 cuz there are no repetitions) and case 2 produces min results (i.e. 1+f)
a+e < 1 + ne (f == ne)
on reducing the equation we get
a < 1 + (n-1)*e (note : n >= 2) and this equation is true
and also one of the two brackets should only contain the max or the second max element.
In cases like {10, 14, 15} we have to split it like {14} and {10, 15}.
we will simply calculate GCD from the first element to the 3rd last element (inclusive) , let’s call that g. Here v[n-1] refers to the last element or max element and v[n-2] refers to 2nd max element. we’ll use an if statement to check which combination produces maximum output.
int gcd_a = __gcd(g,v[n-2])+v[n-1];
int gcd_b = __gcd(g,v[n-1])+v[n-2];
if (gcd_a >= gcd_b)
cout << gcd_a << '\n';
else
cout << gcd_b << '\n';
@anon55659401 my approach of exactly same as above approach, but the approach u said can u prove mathematically. And why then Teja sir didn’t think for your approach ( means I think your approach is simply an observation).
Hello sir,
please provide the input that fails my code
below is my approach
Fact 1:-GCD of a set never greater than the minimum element
Fact 2:-removing an element from the set can effect the GCD of the set
Fact 3:-Fact 2 is not always true for the max element of the set
1)finding min and max elements of the set
2)divide the set based on the GCD example:S={6,10,12} leads to two sets gcd(2)={10},gcd(6)={12}
3)gcd(1) set plays the important role
4)If the set gcd(1) conatins more than one element
then result=1+max,since we have 2 elements that leads to GCD 1,we can keep all elements with gcd 1 elemets in one set and the max element in the other set
5)if the set gcd(1) having only one element
then merge the gcd sets from step 2,after merging gcd(2) ngcd(6) it gives gcd 2
now compare the result=MAX(gcd(after merge) +only element from gcd(1) ,1+max)
6)if the gcd(1) set not exisit
then find the gcd without max element of complete set and find a element that contributing more to the gcd .
gcd without max element forms 2 sets one with only max element and other is with rest
From the Fact 3:-we are finding an element that contribute more the gcd and remove that from the set and find the gcd of the set that is not having that element
that element is need not be the second max
result is which is more
Link to the solution:- https://www.codechef.com/viewsolution/24891558
My approach, please give me a counter example if I’m wrong.
If input is of the form A A A A A A then answer is 2A
If it’s of the form A A A A A B B B B B then answer is A+B
In the third case first sort the input and get A A A A B B B C C D E E F F G H… (this is the sorted version of the input i.e A >B > C …
Now the answer is either A + gcd(B, C, D, E …) or B + gcd(A, C, D, E …). So we have to output the greater of these two values.
Here is my solution. It’s giving TLE. First let me know if my method is correct, if not please give an counter example. And if yes, then let me know the shortest method to implement my program so I don’t get TLE.
Any help will be appreciated.
long long int gcd(long long int a, long long int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int main() {
int t;
cin>>t;
while (t–)
{
long int n;
cin>>n;
long long int a[n],last,slast,op1,op2;
for (long int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
last=a[n-1];
slast=a[n-2];
long long int result = a[0];
for (long int i = 1; i < n-2; i++)
result = gcd(a[i], result);
op1=gcd(result,last)+slast;
op2=gcd(result,slast)+last;
if (op1>=op2)
cout<<op1<<endl;
else
cout<<op2<<endl;
