For this problem: CodeChef: Practical coding for everyone
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?
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