Longest Subarray with GCD Greater than 1

Explanation

Let’s understand the problem statement with the help of an example. Suppose ‘ARR’ is {3, 6, 2} then all possible subarrays with their GCD are:

• {3}, GCD is 3.
• {3, 6}, GCD is 3.
• {3, 6, 2}, GCD is 1.
• {6}, GCD is 6.
• {6, 2}, GCD is 3.
• {2}, GCD is 2.

Out of all the subarray’s shown above, only {3,6} and {6,2} have lengths two and GCD greater than 1. Hence in this example, our answer is 2.

Approach

The naive approach to solve this problem is to check each subarray formed from ‘ARR’ and take one whose length is maximum and whose GCD is greater than 1.

Algorithm

1. Declare the variable ‘ANS’ and initialize it to 0.
2. Create a function getMaxLength() that takes vector ‘ARR’ as argument.
3. Create a variable, ‘ANS’ and initialize it with 0. It will store the length of the longest subarray having GCD > 1.
4. Inside the function getMaxLength(), find the GCD of each subarray by iterating loop inside the loop and using STL __gcd() function and replace ‘ANS’ with the length of subarray if the GCD of that subarray is greater than one and size is greater than ‘ANS’.
5. Return ‘ANS’. 

Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function that returns the length of longest subarray having GCD > 1.
void getLongestSubarrayLen(vector<int> &arr)
{
   // To store the length of the longest subarray having GCD > 1
   int ans = 0;

   // Iterating every subarray.
   for (int i = 0; i < arr.size(); i++)
   {
       // For storing the gcd of each subarray.
       int gcdSubarray = arr[i];

       for (int j = i; j < arr.size(); j++)
       {
           gcdSubarray = __gcd(temp, arr[j]);

           // Check whether 'GCD_SUBARRAY' is greater than 1 or not.
           if (gcdSubarray > 1)
           {
               // Update the 'ANS'.
               ans = max(ans, j - i + 1);
           }
       }
   }
   return ans;
}

int main()
{
   // Taking no. of elements in the array as an input.
   int n;
   cin >> n;

   // Taking 'ARR' as an input.
   vector<int> arr(n);
   for (int i = 0; i < N; i++)
   {
       cin >> arr[i];
   }

   // Calling function 'getLongestSubarrayLen()'.
   int ans = getLongestSubarrayLen(arr);;

   // Print the answer.
   cout << ans;
   return 0;
}

Input

7
2 4 3 5 6 2 2

Output

3

Time Complexity

O(N^2 * log(M)), where ‘N’ is the ‘ARR’ size and M is the largest value in the array.

As creating all the subarray of an array takes O(N ^ 2) time and there are total N ^ 2 subarrays and calling gcd function takes O(log(M)) time. Hence its time complexity is O(N ^ 2 * log(M)).

Space Complexity

O(1).

As we didn’t use extra space except for a few variables.

Key Takeaways

In this blog, we have learned a problem longest subarray with GCD greater than 1. Here, we have discussed the brute force approach to find our result. We saw that the time complexity of this approach is O(N ^ 2).

Check out this problem - Longest Subarray With Sum K 

If you want to learn more about such topics then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!