Problem Code: CORE2002 Help

For this problem: https://www.codechef.com/CORE2020/problems/CORE2002
I’m unable to understand the logic. Is multiple answer possible?

Let’s say I’ve an array : {8,3,2,4}.

Case 1 : If I remove subarray {3,2}, left is {8,4}. Reversing the array results in {4,8}. Max GCD after operations is 4.

Case 2 : If I remove subarray {2,4}, left is {8,3}. Reversing the array results in {3,8}. Max GCD after operations is 1.

I don’t understand the use of reverse operation? How is it Changing the answer?

1. if u notice, reversing array does not affect gcd, gcd is independent of ordering
2. what do you think happens when we have say a number a, and we compute gcd(a, b) where b is another number. this thing cannot be greater than a. and unless b is equal to a, this thing will be less than a. so we want to exclude as many elements as we can.
3. now, since resulting array cannot be empty and we want to remove maximum numbers, we either remove all elements after first or all before last in the array.
so result is max(a[0],a[n-1])
1 Like

Reversing Array operation is just for distraction. This doesn’t effect GCD in any way.

You must know that, GCD(a1,a2,a3…aN) <= min(a1,a2,a3…aN)

Anytime you remove an subarray, you will always have an endpoint left, i.e. remaining array will either have a1 or aN.

so GCD <= a1 or GCD <=aN,
so you choose to remove subarray such that, you get max(a1,aN).

1 Like

It doesn’t.