Number of Subarrays With LCM Equal to K - Video Solutions

Problem Overview: You are given an integer array nums and an integer k. The task is to count how many contiguous subarrays have a Least Common Multiple (LCM) exactly equal to k. A subarray contributes to the answer only if the LCM of all its elements equals k.

Approach 1: Brute Force Enumeration (O(n² log k) time, O(1) space)

Start every subarray from index i and extend it to the right. Maintain the running LCM while iterating j from i to n-1. The LCM of two numbers is computed using lcm(a,b) = (a * b) / gcd(a,b). Each time the running LCM becomes exactly k, increment the answer. If the LCM exceeds k or k % currentLCM != 0, further expansion cannot produce k, so you stop early for that starting index. This direct enumeration checks all possible subarrays and works well for small inputs.

Approach 2: Optimized Expansion with Prefix LCM Pruning (O(n log k) time, O(1) space)

The key observation: if the current LCM ever becomes greater than k or is not a divisor of k, extending the subarray will never bring it back to k. Use the same outer loop for starting index i, but aggressively prune expansions based on this property. Maintain a running LCM while extending the subarray and stop immediately once the divisor condition fails. Because LCM values grow quickly, the inner loop usually runs only a few iterations, making the practical complexity close to linear. All LCM calculations rely on fast gcd operations from number theory.

This approach leverages properties of math and number theory to avoid exploring impossible states. The array itself is processed sequentially using simple iteration patterns common in array problems.

Recommended for interviews: Interviewers expect the optimized expansion approach. The brute force method demonstrates that you understand how to compute LCM incrementally across subarrays. The optimized version shows deeper insight into number theory constraints, specifically the observation that valid LCMs must divide k. That pruning reduces unnecessary checks and brings the complexity close to O(n log k), which is typically the intended solution.