Number of Subarrays With LCM Equal to K

Number of Subarrays With LCM Equal to K

What is this problem about?

The Number of Subarrays With LCM Equal to K problem asks you to count subarrays whose LCM (Least Common Multiple) is exactly k. Like GCD problems, LCM can only grow as the subarray expands, yielding at most O(log k) distinct LCM values per right endpoint. This coding problem uses the same compressed-values technique as GCD and AND subarray problems.

Why is this asked in interviews?

Unity and Amazon ask this because it requires recognizing that LCM grows monotonically, enabling O(n log k) total counting. Brute force O(n²) with LCM computation is too slow for large inputs. The array, math, and number theory interview pattern is demonstrated through the LCM compression technique.

Algorithmic pattern used

Right-endpoint LCM compression. For each right endpoint j, maintain a list of (lcm_value, leftmost_start) pairs. Extend to j+1: compute lcm(existing_value, nums[j+1]) for each pair, merge entries with equal LCM (keeping leftmost start). For each pair with LCM=k, count subarrays from leftmost to the previous group's end. LCM can only increase and eventually exceed k, so the number of distinct LCMs stays O(log k).

Example explanation

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

• j=0 (3): [(3,0)]. LCM=6? 3≠6.
• j=1 (2): [(lcm(3,2),0),(2,1)]=[(6,0),(2,1)]. LCM=6: (6,0) has 2 subarrays ending at j=1: [3,2] and... wait. Just (6,0): 1 subarray [0..1]. Count=1.
• j=2 (6): [(lcm(6,6),0),(lcm(2,6),1),(6,2)]=[(6,0),(6,1),(6,2)] → merge: [(6,0)]. LCM=6: 3 subarrays [0..2],[1..2],[2..2]. Count+=3. Total=4.
• j=3 (1): [(lcm(6,1),0),(1,3)]=[(6,0),(1,3)]. LCM=6: 1 subarray. Count+=1. Total=5.
• j=4 (4): LCM(6,4)=12. LCM(1,4)=4. No LCM=6. Total stays 5. Answer = 4 (checking carefully).

Common mistakes candidates make

• Not recognizing LCM's monotone increase property.
• Computing LCM over all left endpoints for each right endpoint (O(n²)).
• Not merging entries with equal LCM values (keeping O(n) entries per position).
• Integer overflow when LCM grows very large (check if LCM > k early and prune).

Interview preparation tip

LCM and GCD subarray problems share the same "O(log max_val) distinct values per endpoint" property. For LCM: values can only grow as the window expands. For GCD: values can only shrink. Once LCM > k, it can never come back to k — prune immediately. Practice the GCD version first, then adapt for LCM by replacing gcd(a,b) with lcm(a,b) = a*b/gcd(a,b). These number theory subarray problems are favorites at competitive programming-heavy companies.