Maximum Length Subarray with Given GCD
Problem Statement
You are given an integer array arr and an integer k.
Your task is to find the maximum length of a contiguous subarray whose GCD (Greatest Common Divisor) is exactly equal to k.
Example 1
Input
arr = [2, 4, 6, 8], k = 2
Output
4
Explanation
GCD of entire array = 2
Example 2
Input
arr = [3, 6, 9, 12], k = 3
Output
4
Example 3
Input
arr = [2, 4, 8, 16], k = 4
Output
3
Subarray [4, 8, 16]
Why This Problem Is Important
- Tests understanding of GCD properties
- Introduces subarray compression using GCD
- Common in Google, Codeforces, LeetCode
- Foundation for range-GCD optimization problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Brute Force | Check all subarrays | O(n² log M) | O(1) |
| Optimized | GCD compression | O(n log M) | O(log M) |
(M = maximum element value)
Approach 1 -Brute Force Approach
Idea
- Consider every subarray
- Maintain running GCD
- If GCD becomes less than k, break
- If GCD equals k, update answer
Time and Space Complexity
- Time: O(n² log M)
- Space: O(1)
Python Implementation
import math
def maxLenSubarrayGCD(arr, k):
n = len(arr)
ans = 0
for i in range(n):
g = 0
for j in range(i, n):
g = math.gcd(g, arr[j])
if g < k:
break
if g == k:
ans = max(ans, j - i + 1)
return ans
C++ Implementation
#include
using namespace std;
int maxLenSubarrayGCD(vector& arr, int k){
int n = arr.size();
int ans = 0;
for(int i=0;iJava Implementation
class Main {
static int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
static int maxLenSubarrayGCD(int[] arr, int k){
int n = arr.length;
int ans = 0;
for(int i=0;iJavaScript Implementation
function gcd(a, b){
while(b !== 0){
let t = b;
b = a % b;
a = t;
}
return a;
}
function maxLenSubarrayGCD(arr, k){
let n = arr.length;
let ans = 0;
for(let i=0;iC# Implementation
static int GCD(int a, int b){
while(b != 0){
int t = b;
b = a % b;
a = t;
}
return a;
}
static int MaxLenSubarrayGCD(int[] arr, int k){
int n = arr.Length;
int ans = 0;
for(int i=0;iOutput
2Approach 2- Optimized Approach (GCD Compression)
Idea
- For each index, maintain a map of {gcd_value : max_length}
- Extend previous subarrays by current element
- GCD values reduce fast (log M)
- Track longest subarray where GCD equals k
Time and Space Complexity
- Time: O(n log M)
- Space: O(log M)
Python Implementation
import math
def maxLenSubarrayGCD(arr, k):
ans = 0
prev = {}
for num in arr:
curr = {}
curr[num] = 1
for g, length in prev.items():
new_g = math.gcd(g, num)
curr[new_g] = max(curr.get(new_g, 0), length + 1)
if k in curr:
ans = max(ans, curr[k])
prev = curr
return ans
C++ Implementation
#include
using namespace std;
int maxLenSubarrayGCD(vector& arr, int k){
unordered_map prev, curr;
int ans = 0;
for(int num : arr){
curr.clear();
curr[num] = 1;
for(auto &p : prev){
int g = gcd(p.first, num);
curr[g] = max(curr[g], p.second + 1);
}
if(curr.count(k))
ans = max(ans, curr[k]);
prev = curr;
}
return ans;
}
Java Implementation
import java.util.*;
class Main {
static int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}
static int maxLenSubarrayGCD(int[] arr, int k){
Map prev = new HashMap<>();
int ans = 0;
for(int num : arr){
Map curr = new HashMap<>();
curr.put(num, 1);
for(Map.Entry e : prev.entrySet()){
int g = gcd(e.getKey(), num);
curr.put(g, Math.max(curr.getOrDefault(g, 0), e.getValue() + 1));
}
if(curr.containsKey(k))
ans = Math.max(ans, curr.get(k));
prev = curr;
}
return ans;
}
}
JavaScript Implementation
function gcd(a, b){
while(b !== 0){
let t = b;
b = a % b;
a = t;
}
return a;
}
function maxLenSubarrayGCD(arr, k){
let prev = new Map();
let ans = 0;
for(let num of arr){
let curr = new Map();
curr.set(num, 1);
for(let [g, len] of prev){
let ng = gcd(g, num);
curr.set(ng, Math.max(curr.get(ng) || 0, len + 1));
}
if(curr.has(k))
ans = Math.max(ans, curr.get(k));
prev = curr;
}
return ans;
}
C# Implementation
static int GCD(int a, int b){
while(b != 0){
int t = b;
b = a % b;
a = t;
}
return a;
}
static int MaxLenSubarrayGCD(int[] arr, int k){
Dictionary prev = new Dictionary();
int ans = 0;
foreach(int num in arr){
Dictionary curr = new Dictionary();
curr[num] = 1;
foreach(var p in prev){
int g = GCD(p.Key, num);
curr[g] = Math.Max(curr.ContainsKey(g) ? curr[g] : 0, p.Value + 1);
}
if(curr.ContainsKey(k))
ans = Math.Max(ans, curr[k]);
prev = curr;
}
return ans;
}
Output
2Final Summary
| Approach | Use Case |
|---|---|
| Brute Force | Small constraints |
| Optimized GCD | Interview standard |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
