# Number of Subarrays With LCM Equal to K **Difficulty:** MEDIUM [External](https://leetcode.com/problems/number-of-subarrays-with-lcm-equal-to-k) Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-with-lcm-equal-to-k **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory) **Data structures:** Array **Companies:** [Unity](https://scaleengineer.com/companies/unity) --- ## Problem 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. **Example 1:** **Input:** nums = [3,6,2,7,1], k = 6 **Output:** 4 **Explanation:** The subarrays of nums where 6 is the least common multiple of all the subarray's elements are: - [**3**,**6**,2,7,1] - [**3**,**6**,**2**,7,1] - [3,**6**,2,7,1] - [3,**6**,**2**,7,1] **Example 2:** **Input:** nums = [3], k = 2 **Output:** 0 **Explanation:** There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements. **Constraints:** * `1 <= nums.length <= 1000` * `1 <= nums[i], k <= 1000` # Approaches ## Brute Force with Optimization This approach iterates through all possible contiguous subarrays using a pair of nested loops. For each subarray, it calculates the Least Common Multiple (LCM) of its elements and checks if it equals `k`. The process is optimized by pruning the search space early. **Time:** O(N^2 * log(K)). There are two nested loops, giving a factor of `O(N^2)`. Inside the inner loop, we compute the LCM, which involves a GCD calculation. GCD of two numbers `a` and `b` takes `O(log(min(a, b)))` time. Since the numbers involved in the LCM calculation do not exceed `k`, this operation takes `O(log(K))` time. · **Space:** O(1) extra space. We only use a few variables to store the count and the current LCM. **Pros:** Relatively simple to understand and implement.; Efficient enough to pass given the problem constraints (`N <= 1000`). **Cons:** The `O(N^2)` time complexity can be too slow if the constraints on `N` were larger. ### Explanation The brute-force method involves generating every subarray and checking its LCM. We can optimize this by using two nested loops. The outer loop with index `i` fixes the starting element of a subarray, and the inner loop with index `j` extends the subarray to the right.\n\nFor each starting position `i`, we iteratively build the subarray and maintain the LCM of its elements so far (`currentLcm`). As we include `nums[j]` into the subarray `nums[i...j]`, we update `currentLcm = lcm(currentLcm, nums[j])`. If this `currentLcm` equals `k`, we've found a valid subarray.\n\nTo improve efficiency, we apply two key optimizations:\n1. If we encounter an element `nums[j]` that is not a divisor of `k`, we can immediately stop extending the current subarray (i.e., break the inner loop). This is because for the LCM of a set of numbers to be `k`, every number in that set must be a divisor of `k`.\n2. If the `currentLcm` exceeds `k` at any point, we can also stop. The LCM is a non-decreasing function as we add more elements, so it will never go back down to `k`.\n\n```java\nclass Solution {\n public int subarrayLCM(int[] nums, int k) {\n int n = nums.length;\n int count = 0;\n for (int i = 0; i < n; i++) {\n long currentLcm = 1;\n for (int j = i; j < n; j++) {\n if (k % nums[j] != 0) {\n break;\n }\n currentLcm = lcm(currentLcm, nums[j]);\n if (currentLcm == k) {\n count++;\n }\n if (currentLcm > k) {\n break;\n }\n }\n }\n return count;\n }\n\n private long gcd(long a, long b) {\n while (b != 0) {\n long temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n }\n\n private long lcm(long a, long b) {\n if (a == 0 || b == 0) {\n return 0;\n }\n if (a == 1) return b;\n if (b == 1) return a;\n // To avoid overflow, divide first\n return (a / gcd(a, b)) * b;\n }\n}\n``` ### Algorithm - Initialize a counter `count` to 0.\n- Define helper functions for `gcd(a, b)` and `lcm(a, b)`. The `lcm` function should be careful about potential overflows, for example by computing `(a / gcd(a, b)) * b`.\n- Loop for `i` from `0` to `n-1` (this will be the start of the subarray):\n - Initialize `currentLcm = 1`.\n - Loop for `j` from `i` to `n-1` (this will be the end of the subarray):\n - **Optimization 1:** If `k` is not divisible by `nums[j]`, then `nums[j]` cannot be in a subarray whose LCM is `k`. Since all subsequent subarrays starting at `i` will also contain `nums[j]`, we can `break` the inner loop.\n - Update `currentLcm` by computing the least common multiple of `currentLcm` and `nums[j]`.\n - If `currentLcm` is equal to `k`, increment `count`.\n - **Optimization 2:** If `currentLcm` becomes greater than `k`, it can never become `k` again by including more elements. So, we can `break` the inner loop.\n- Return the total `count`. ## Iterating Endpoints with LCM Map This is a more efficient approach that uses a dynamic programming-like strategy. It iterates through the array from left to right. For each element `nums[j]`, it efficiently calculates how many subarrays *ending* at `j` have an LCM of `k` by leveraging the results from subarrays ending at `j-1`. **Time:** O(N * D_k * log(K)), where `N` is the array length, `D_k` is the number of divisors of `k`. For each of the `N` elements, we iterate through the `prevLcms` map, whose size is bounded by `D_k`. Inside this loop, the `lcm` calculation takes `O(log(K))` time. As `D_k` is small, the overall complexity is very efficient. · **Space:** O(D_k), where `D_k` is the number of divisors of `k`. The space is dominated by the maps used to store LCM counts. Since `k <= 1000`, `D_k` is a small constant (at most 32). **Pros:** Highly efficient with a time complexity that is nearly linear in the size of the input array.; Scales well even for larger constraints on `N`. **Cons:** More complex to reason about and implement compared to the brute-force approach.; Uses extra space for the map, although the space is small. ### Explanation Instead of re-calculating from scratch for every subarray, we can build upon previous calculations. We iterate through the array with a single loop, fixing the end element `nums[j]` of our subarrays.\n\nWe maintain a map, `prevLcms`, which stores the distinct LCM values of all subarrays ending at the previous index `j-1`, along with how many subarrays produced each LCM. For example, `{lcm_val -> count}`.\n\nWhen we move to the current element `nums[j]`, we construct a new map `currLcms` for subarrays ending at `j`. This new map is formed by:\n1. Considering `nums[j]` as a subarray of its own. Its LCM is `nums[j]`.\n2. Extending all subarrays that ended at `j-1`. For each `(lcm, count)` in `prevLcms`, we form new subarrays by appending `nums[j]`. The new LCM will be `lcm(lcm, nums[j])`.\n\nAfter constructing `currLcms`, the number of new subarrays ending at `j` with an LCM of `k` is simply the count associated with the key `k` in our new map. We add this to our total result.\n\nThe efficiency of this method stems from a key insight: the number of distinct LCM values for subarrays ending at any index `j` is small. Since we only care about subarrays with an LCM of `k`, any intermediate LCM must be a divisor of `k`. The number of divisors for any integer up to 1000 is very small (e.g., 840 has 32 divisors), so the size of our map remains small.\n\n```java\nclass Solution {\n public int subarrayLCM(int[] nums, int k) {\n int ans = 0;\n Map prevLcms = new HashMap<>();\n\n for (int num : nums) {\n Map currLcms = new HashMap<>();\n if (k % num == 0) {\n // Subarray with just the current number\n currLcms.put(num, 1);\n\n // Extend previous subarrays\n for (Map.Entry entry : prevLcms.entrySet()) {\n int prevLcm = entry.getKey();\n int count = entry.getValue();\n int newLcm = (int) lcm(prevLcm, num);\n if (k % newLcm == 0) {\n currLcms.put(newLcm, currLcms.getOrDefault(newLcm, 0) + count);\n }\n }\n }\n // If k % num != 0, currLcms remains empty, effectively resetting the state.\n ans += currLcms.getOrDefault(k, 0);\n prevLcms = currLcms;\n }\n return ans;\n }\n\n private long gcd(long a, long b) {\n while (b != 0) {\n long temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n }\n\n private long lcm(long a, long b) {\n if (a == 0 || b == 0) return 0;\n long res = (a / gcd(a, b)) * b;\n // We only care about LCMs <= k. If res > k, it will be filtered out\n // by the k % newLcm == 0 check, since k % res would be k, not 0.\n return res;\n }\n}\n``` ### Algorithm - Initialize `totalCount = 0`.\n- Initialize a map `prevLcms` to store `{lcm -> count}` pairs for subarrays ending at the previous index.\n- Loop through the array with index `j` from `0` to `n-1`:\n - Initialize a new map `currLcms`.\n - If `k % nums[j] == 0` (if not, `nums[j]` acts as a separator, and `currLcms` remains empty, effectively resetting the process):\n - Add `(nums[j], 1)` to `currLcms`. This corresponds to the subarray containing only `nums[j]`.\n - For each `(lcm, count)` pair in `prevLcms`:\n - Calculate `newLcm = lcm(lcm, nums[j])`.\n - If `k % newLcm == 0`, it means `newLcm` is a divisor of `k`. Add `count` to the value of `newLcm` in `currLcms`.\n - Add the count for `k` from `currLcms` (i.e., `currLcms.getOrDefault(k, 0)`) to `totalCount`.\n - Update `prevLcms = currLcms` for the next iteration.\n- Return `totalCount`. # Solutions ### Java ```java class Solution { public int subarrayLCM(int[] nums, int k) { int n = nums.length; int ans = 0; for (int i = 0; i < n; ++i) { int a = nums[i]; for (int j = i; j < n; ++j) { int b = nums[j]; int x = lcm(a, b); if (x == k) { ++ans; } a = x; } } return ans; } private int lcm(int a, int b) { return a * b / gcd(a, b); } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } ``` ### CPP ```cpp class Solution { public: int subarrayLCM(vector &nums, int k) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) { int a = nums[i]; for (int j = i; j < n; ++j) { int b = nums[j]; int x = lcm(a, b); ans += x == k; a = x; } } return ans; } }; ``` ### Python ```python class Solution: def subarrayLCM(self, nums: List[int], k: int) -> int: n = len(nums) ans = 0 for i in range(n): a = nums[i] for b in nums[i:]: x = lcm(a, b) ans += x == k a = x return ans ```