Number of Subarrays With LCM Equal to K

Problem Description

Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of the subarray's elements is k. A subarray is a contiguous non-empty sequence of elements within an array. The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.

Key Insights

• A subarray's least common multiple (LCM) can be computed incrementally as new elements are added.
• If the LCM of a subarray exceeds k, further elements cannot reduce the LCM to k.
• Only elements that are factors of k can contribute to forming subarrays with LCM equal to k.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case, where n is the length of the input array.
Space Complexity: O(1), as we only use a constant amount of extra space.

Solution

To solve the problem, we can use a nested loop approach where we iterate over each possible starting point of the subarray and expand to the right, calculating the LCM as we go. We keep track of the count of subarrays where the LCM equals k. The key steps are:

1. Begin with an outer loop to select the start index of the subarray.
2. Use an inner loop to expand the subarray and compute the LCM.
3. If at any point the LCM exceeds k, break out of the inner loop as further elements will only increase the LCM.
4. Count the number of valid subarrays whose LCM equals k.

Code Solutions