Number of Subarrays With GCD Equal to K

Number of Subarrays With GCD Equal to K

What is this problem about?

The Number of Subarrays With GCD Equal to K problem asks you to count subarrays whose GCD is exactly k. This coding problem exploits the fact that as a subarray grows, the GCD can only decrease or stay the same — yielding O(log max_val) distinct GCD values per right endpoint.

Why is this asked in interviews?

Amazon asks this because it demonstrates the "at most O(log max_val) distinct GCDs" property, enabling efficient O(n log n) counting instead of O(n²). The array, math, and number theory interview pattern is directly applied with GCD monotonicity as the key insight.

Algorithmic pattern used

Right endpoint scan with GCD compression. For each right endpoint j, maintain a list of (gcd_value, leftmost_start) pairs for subarrays ending at j. Extend to j+1 by computing gcd of each pair's value with nums[j+1]. Merge entries with equal GCD values (keeping leftmost start). For each pair with GCD=k, count the subarrays (rightmost_start - leftmost_start + 1).

Example explanation

nums=[9,3,1,2,6,3], k=3.

• j=0 (9): [(9,0)]. GCD=3? 9≠3.
• j=1 (3): [(gcd(9,3),0),(3,1)] = [(3,0),(3,1)] → merge: [(3,0)]. GCD=3 ✓. Count starts from 0 to 1 = 2 subarrays: [9,3],[3].
• j=2 (1): [(gcd(3,1),0),(1,2)] = [(1,0),(1,2)] → merge: [(1,0)]. No GCD=3. Continue for all j. Total subarrays with GCD=3 = 4.

Common mistakes candidates make

• O(n²) brute force computing GCD for all subarrays explicitly.
• Not merging GCD entries (keeping O(n) entries per position).
• Confusing "GCD equals k" with "GCD is divisible by k."
• Incorrect counting of subarrays from leftmost/rightmost start positions.

Interview preparation tip

GCD subarray problems mirror AND subarray problems in their O(log max_val) distinct-values property. The pattern is identical: maintain (value, start) pairs, merge on equal values when extending. For GCD-equals-k counting, this gives O(n log n) overall. Practice this "compressed values" technique for GCD, LCM, AND, OR — they all share the same monotone decrease/increase property that enables efficient subarray enumeration. DE Shaw and Amazon frequently test these advanced bit/number theory subarray problems.