Prerequisite : Number Theory, Binary Search, Two Pointer, Prefix Sum
Problem statement summary : You are given an Array A[] of length N. You need to find out the length of the longest subarray where the GCD of the subarray is greater than X.
Solution : If you have noticed , X and all elements of the array are less than or equal 100.
For each i is 1<= i <= 100, we can calculate in a 2d array , total cost for which gcd we want to make.
For example, if we want to make gcd = 3, and subarray is looking like A = {1 , 2, 1};
For position 1, we need to increase 2 times, A ={ 3, 2, 1}
For position 2, we need to increase 1 times, A = {3, 3, 1}
For position 3, we need to increase 2 times, A ={ 3, 3,3} , gcd = 3.
Total cost for each position we can save an array.
In each subarray, We can use binary search, because we have limit of cost K.
For each, i > X , Find the best subarray which length is maximum and total cost is less than or equal K.
Time Complexity : O ( 100 * N * log (N) ).
Instead of Binary Search we can use two pointer, time complexity has less than above solution and its complexity: O (100 * N). check ->(Tester Code) in Solution section.