Problem Description :
Given an array of N integers we have to find the largest subarray with maximal gcd .
Problem Type : Easy / Adhoc type
Short Explanation :
Let the maximal number in the array be " M " .We have to find the largest subarray with all its numbers being M .
Detailed Explanation :
We first have to see what the maximal gcd of the array can be .
It can simply be found by traversing the array and finding the maximal number .To find the largest subarray with maximal gcd we simply have to find the largest subarray with all its numbers being the maximum number of the array .
This can be done in O(n) by simply increasing the counter if maximum number found otherwise setting it to zero . In the end the maximum subarray is the answer .
Complexity :O(n)
Solution :https://ideone.com/ZVZsu3
Related Problems :
Practice : https://www.codechef.com/problems/BYTES11
Contest : https://www.codechef.com/BYTE2016/problems/BYTES11