Longest sub-array with maximum GCD
Given an array arr[] of length N, the task is the find the length of the longest sub-array with the maximum possible GCD value.
Examples:
Input: arr[] = {1, 2, 2}
Output: 2
Here all possible sub-arrays and there GCD’s are:
1) {1} -> 1
2) {2} -> 2
3) {2} -> 2
4) {1, 2} -> 1
5) {2, 2} -> 2
6) {1, 2, 3} -> 1
Here, the maximum GCD value is 2 and longest sub-array having GCD = 2 is {2, 2}.
Thus, the answer is {2, 2}.
Input: arr[] = {3, 3, 3, 3}
Output: 4
Naive approach:
This method’s temporal complexity is O(n^3), where n is the length of the input array, making it inefficient for large inputs. This is because each sub-array’s GCD was calculated using nested loops that generated all of the sub-arrays.
Follow the steps:
- Generate all sub-arrays
- Calculate GCD for each sub-array
- Check for maximum GCD value, and update the maximum gcd and maximum length accordingly.
- Return the maximum length
Below is the implementation of the above approach:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to calculate the greatest common divisor (GCD) of two numbers
int gcd(int a, int b) {
while (b) {
a %= b;
swap(a, b); // Swapping values to continue the process
}
return a; // Return the GCD
}
// Function to find the length of the longest sub-array with maximum GCD value (naive approach)
int longestSubarrayNaive(vector<int>& arr) {
int n = arr.size(); // Length of the input array
int maxLength = 0; // Initialize the maximum length of sub-array
int maxGcd=0;
// Nested loops to generate all possible sub-arrays
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
int subarrayGcd = arr[i]; // Initialize GCD value with the first element of the sub-array
// Loop to calculate GCD of the sub-array elements
for (int k = i + 1; k <= j; ++k) {
subarrayGcd = gcd(subarrayGcd, arr[k]); // Update GCD value iteratively
}
if (subarrayGcd > maxGcd) {
maxLength = j - i + 1; // Update the maximum length if condition satisfies
maxGcd=subarrayGcd;
}
else if(subarrayGcd == maxGcd)
{
maxLength = max(maxLength, j - i + 1);
}
}
}
return maxLength; // Return the length of the longest sub-array with maximum GCD
}
int main() {
vector<int> arr1 = {1, 2, 2};
vector<int> arr2 = {3, 3, 3, 3};
// Example usage
cout << "Longest sub-array length for arr1: " << longestSubarrayNaive(arr1) << endl; // Output: 2
cout << "Longest sub-array length for arr2: " << longestSubarrayNaive(arr2) << endl; // Output: 4
return 0;
}
import java.util.Arrays;
public class Main {
static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static int longestSubarrayNaive(int[] arr) {
int n = arr.length;
int maxLength = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int subarrayGcd = arr[i];
for (int k = i + 1; k <= j; k++) {
subarrayGcd = gcd(subarrayGcd, arr[k]);
}
if (subarrayGcd == Arrays.stream(arr, i, j + 1).max().getAsInt()) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 2 };
int[] arr2 = { 3, 3, 3, 3 };
System.out.println("Longest sub-array length for arr1: " + longestSubarrayNaive(arr1)); // Output: 2
System.out.println("Longest sub-array length for arr2: " + longestSubarrayNaive(arr2)); // Output: 4
}
}
# Function to calculate the greatest common divisor (GCD) of two numbers
def gcd(a, b):
while b:
a, b = b, a % b
return a
# Function to find the length of the longest sub-array with maximum GCD value (naive approach)
def longest_subarray_naive(arr):
n = len(arr) # Length of the input array
max_length = 0 # Initialize the maximum length of sub-array
# Nested loops to generate all possible sub-arrays
for i in range(n):
for j in range(i, n):
subarray = arr[i:j+1] # Generate sub-array from index i to j (inclusive)
subarray_gcd = subarray[0] # Initialize GCD value with the first element of the sub-array
# Loop to calculate GCD of the sub-array elements
for k in range(1, len(subarray)):
subarray_gcd = gcd(subarray_gcd, subarray[k]) # Update GCD value iteratively
# Check if the GCD of the sub-array equals the maximum element of the sub-array
if subarray_gcd == max(subarray):
max_length = max(max_length, len(subarray)) # Update the maximum length if condition satisfies
return max_length # Return the length of the longest sub-array with maximum GCD
# Example usage
arr1 = [1, 2, 2]
arr2 = [3, 3, 3, 3]
print("Longest sub-array length for arr1:", longest_subarray_naive(arr1)) # Output: 2
print("Longest sub-array length for arr2:", longest_subarray_naive(arr2)) # Output: 4
function gcd(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function longestSubarrayNaive(arr) {
const n = arr.length;
let maxLength = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let subarrayGcd = arr[i];
for (let k = i + 1; k <= j; k++) {
subarrayGcd = gcd(subarrayGcd, arr[k]);
}
if (subarrayGcd === Math.max(...arr.slice(i, j + 1))) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}
const arr1 = [1, 2, 2];
const arr2 = [3, 3, 3, 3];
console.log("Longest sub-array length for arr1:", longestSubarrayNaive(arr1)); // Output: 2
console.log("Longest sub-array length for arr2:", longestSubarrayNaive(arr2)); // Output: 4
Output
Longest sub-array length for arr1: 2 Longest sub-array length for arr2: 4
Time Complexity : O(n^3), where n is the length of the input array.
Auxilary Space: O(1)
Optimal approach:
The maximum GCD value will always be equal to the largest number present in the array. Let’s say that the largest number present in the array is X. Now, the task is to find the largest sub-array having all X. The same can be done using the two-pointer approach.
Below is the algorithm:
- Find the largest number in the array. Let us call this number X.
- Run a loop from i = 0
- If arr[i] != X then increment i and continue.
- Else initialize j = i.
- While j < n and arr[j] = X, increment j.
- Update the answer as ans = max(ans, j – i).
- Update i as i = j.
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of
// the largest subarray with
// maximum possible GCD
int findLength(int* arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++) {
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (j<n && arr[j] == x)
j++;
// Updating the answer
ans = max(ans, j - i);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2 };
int n = sizeof(arr) / sizeof(int);
cout << findLength(arr, n);
return 0;
}
// Java implementation of the approach
class GFG
{
// Function to return the length of
// the largest subarray with
// maximum possible GCD
static int findLength(int []arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = Math.max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++)
{
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
{
j++;
if (j >= n )
break;
}
// Updating the answer
ans = Math.max(ans, j - i);
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 2, 2 };
int n = arr.length;
System.out.println(findLength(arr, n));
}
}
// This code is contributed by AnkitRai01
# Python3 implementation of the approach
# Function to return the length of
# the largest subarray with
# maximum possible GCD
def findLength(arr, n) :
# To store the maximum number
# present in the array
x = 0;
# Finding the maximum element
for i in range(n) :
x = max(x, arr[i]);
# To store the final answer
ans = 0;
# Two pointer
for i in range(n) :
if (arr[i] != x) :
continue;
# Running a loop from j = i
j = i;
# Condition for incrementing 'j'
while (arr[j] == x) :
j += 1;
if j >= n :
break
# Updating the answer
ans = max(ans, j - i);
return ans;
# Driver code
if __name__ == "__main__" :
arr = [ 1, 2, 2 ];
n = len(arr);
print(findLength(arr, n));
# This code is contributed by AnkitRai01
// C# implementation of the approach
using System;
class GFG
{
// Function to return the length of
// the largest subarray with
// maximum possible GCD
static int findLength(int []arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = Math.Max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++)
{
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
{
j++;
if (j >= n )
break;
}
// Updating the answer
ans = Math.Max(ans, j - i);
}
return ans;
}
// Driver code
public static void Main ()
{
int []arr = { 1, 2, 2 };
int n = arr.Length;
Console.WriteLine(findLength(arr, n));
}
}
// This code is contributed by AnkitRai01
<script>
// Javascript implementation of the approach
// Function to return the length of
// the largest subarray with
// maximum possible GCD
function findLength(arr, n)
{
// To store the maximum number
// present in the array
var x = 0;
// Finding the maximum element
for (var i = 0; i < n; i++)
x = Math.max(x, arr[i]);
// To store the final answer
var ans = 0;
// Two pointer
for (var i = 0; i < n; i++) {
if (arr[i] != x)
continue;
// Running a loop from j = i
var j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
j++;
// Updating the answer
ans = Math.max(ans, j - i);
}
return ans;
}
// Driver code
var arr = [1, 2, 2 ];
var n = arr.length;
document.write( findLength(arr, n));
</script>
Output
2
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array