2470. Number of Subarrays With LCM Equal to K
Problem Description
The problem provides us with two inputs: an array nums of integers and an integer k. We are required to find the number of contiguous non-empty sequences within the array (subarrays), such that the Least Common Multiple (LCM) of the numbers in each of these subarrays is exactly k.
A subarray is a sequence of consecutive elements from the array and has at least one element. It's not necessary for a subarray to include every element from the original array; it could just contain a part of it.
The Least Common Multiple (LCM) of an array is defined as the smallest positive integer divisible by each of the array elements. In other words, each element in the array is a factor of the LCM.
For example, if given nums = [2,3,4] and k = 12, we'd be looking for subarrays like [2,3,4] and [3,4] since the LCMs of these subarrays are 12.
Intuition
The intuition behind the solution is to iteratively explore all possible subarrays and calculate their LCM until we find the subarrays where the LCM is equal to k. This can be done by checking each possible pair of starting and ending positions within the nums array.
We initialize a variable to count the number of desirable subarrays. Starting with the first element of the array, we calculate the LCM of this single element and then extend the subarray one element at a time by including the next element in sequence and updating the LCM of the broader subarray to include this new element. We compare the updated LCM to k. If it's equal, we increment our count.
This process is repeated, expanding the subarray one element at a time, until we've considered all elements from the current starting position. We then shift our starting position by one and repeat the entire process until we've explored all possible starting positions in the array.
The provided solution does not directly call a built-in 'lcm' function since it was pseudocode, where 'lcm' would represent a standard function to calculate the Least Common Multiple. In an actual Python implementation, you would have to define such a function or use math algorithms to calculate the LCM for each step.
Learn more about Math patterns.
Which data structure is used to implement priority queue?
Solution Approach
The implementation begins by setting a counter ans to 0, which will keep a tally of the number of subarrays that have k as their LCM. The outer loop iterates over each start position of a potential subarray within nums. The inner loop then iterates through each end position, starting from the current start position and extending to the end of nums.
No complex data structures are necessary for this approach; we only require variables to store the ongoing LCM (a) and the answer counter (ans).
The lcm(a, b) function is called at each step, which calculates the LCM of the current accumulated LCM value a and the new element b from the array. If lcm(a, b) returns a value that equals k, we know we have found a valid subarray, and we increment ans by 1. The accumulator a is then updated to the new LCM to reflect the LCM of the subarray from the start position to the current position i in nums. This ensures we are always calculating the LCM of the current subarray under consideration.
The algorithm's efficiency could vary widely based on the implementation of the LCM calculation and the range of numbers in nums. It's a brute force approach and may not be efficient for larger arrays or larger values of k due to its time complexity, which is O(n^2) in the number of elements n in nums because of the nested loops. Each extension of the subarray involves computing an LCM, which itself can be costly depending on the size of the numbers involved.
Note: In an actual Python implementation, since the provided pseudocode assumes the existence of an lcm function, one would either define a function to calculate the LCM or utilize a library function such as [math](/problems/math-basics).gcd() to calculate the Greatest Common Divisor (GCD) and then use the relation lcm(a, b) = abs(a*b) // gcd(a, b) to find the LCM of two numbers.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Example Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we are given the following inputs: nums = [2, 6, 8] and k = 24. We want to find all contiguous subarrays where the LCM of the numbers is exactly 24.
-
We start with the first element 2. The LCM of just [2] is 2, which is not equal to 24. So, we move on.
-
Next, we consider the subarray [2, 6]. The LCM of this set is 6 (since 6 is a multiple of 2 and it is the smallest one that is), which is still not equal to 24. We iterate further.
-
Now, we extend our subarray to [2, 6, 8]. The LCM of [2, 6, 8] is 24, which matches k. We increment our counter
ansto 1. -
Since we have reached the end of the array for this starting position, we reset to the next starting position in the array, which is element 6.
-
Starting at the element 6, the LCM of [6] is 6. Since this does not match 24, we continue.
-
We then look at [6, 8]. The LCM of this subarray is 24, which does match k. We increment
ansto 2. -
We've gone through all elements, so we move on to the starting element 8. However, the LCM of [8] is 8, which does not match 24.
After completing the iterations, we find that there are 2 subarrays whose LCM is 24: [2, 6, 8] and [6, 8]. Therefore, the final answer (ans) is 2.
Solution Implementation
1from math import gcd
2from typing import List
3
4class Solution:
5 def subarrayLCM(self, nums: List[int], k: int) -> int:
6 n = len(nums) # Length of the nums list
7 count = 0 # Initialize count of subarrays with LCM equals to k
8
9 # Helper function to calculate LCM of two numbers
10 def lcm(x, y):
11 return (x * y) // gcd(x, y)
12
13 # Iterate over each starting point of subarrays
14 for i in range(n):
15 # Initialize the LCM of the current subarray
16 subarray_lcm = nums[i]
17 # Extend the subarray to include subsequent elements
18 for j in range(i, n):
19 # Calculate the LCM of the current subarray
20 subarray_lcm = lcm(subarray_lcm, nums[j])
21 # Check if the current subarray LCM is equal to k
22 if subarray_lcm == k:
23 count += 1
24 # If LCM exceeds k, no need to continue extending the subarray
25 if subarray_lcm > k:
26 break
27
28 return count # Return the count of valid subarrays
291class Solution {
2 // This method finds the number of contiguous subarrays where the Least Common Multiple (LCM)
3 // of their elements is equal to a given integer k
4 public int subarrayLCM(int[] nums, int k) {
5 int length = nums.length; // Length of the input array
6 int count = 0; // To keep track of the number of subarrays with LCM equal to k
7
8 // Iterate over the array to consider every possible subarray
9 for (int i = 0; i < length; ++i) {
10 int currentLCM = nums[i]; // Initialize the LCM with the first element of subarray
11 // Consider all subarrays starting at index i
12 for (int j = i; j < length; ++j) {
13 int nextElement = nums[j]; // Next element in the subarray to consider
14 currentLCM = lcm(currentLCM, nextElement); // Update the current LCM
15
16 // If the current LCM is equal to k, increment the count
17 if (currentLCM == k) {
18 ++count;
19 }
20 }
21 }
22 return count; // Return the total count of such subarrays
23 }
24
25 // This helper method calculates the Least Common Multiple of two integers a and b
26 private int lcm(int a, int b) {
27 return a * (b / gcd(a, b)); // LCM formula: a * b / GCD(a, b)
28 }
29
30 // This recursive helper method calculates the Greatest Common Divisor of two integers a and b
31 private int gcd(int a, int b) {
32 return b == 0 ? a : gcd(b, a % b); // GCD calculation using Euclidean algorithm
33 }
34}
351#include <numeric> // Required for std::lcm function
2
3class Solution {
4public:
5 // Function to count subarrays whose Least Common Multiple (LCM) is equal to `k`.
6 int subarrayLCM(vector<int>& nums, int k) {
7 int numElements = nums.size(); // Size of the input array
8 int count = 0; // Variable to store the count of valid subarrays
9
10 // Iterate over the array using two pointers to check every subarray's LCM
11 for (int start = 0; start < numElements; ++start) {
12 // Start with the first element of the subarray
13 int currentLCM = nums[start];
14
15 // Expand the subarray towards the right
16 for (int end = start; end < numElements; ++end) {
17 int nextElement = nums[end];
18
19 // Calculate the LCM of the current subarray
20 currentLCM = std::lcm(currentLCM, nextElement);
21
22 // If the LCM is equal to `k`, increment the count
23 if (currentLCM == k) {
24 ++count;
25 }
26 }
27 }
28
29 // Return the total count of subarrays whose LCM is `k`
30 return count;
31 }
32};
331// Import the Math library for Least Common Multiple computation
2import * as Math from "mathjs";
3
4// Function to count subarrays whose Least Common Multiple (LCM) is equal to `k`
5function subarrayLCM(nums: number[], k: number): number {
6 let numElements = nums.length; // Size of the input array
7 let count = 0; // Variable to store the count of valid subarrays
8
9 // Iterate over the array using two pointers to check every subarray's LCM
10 for (let start = 0; start < numElements; ++start) {
11 // Start with the first element of the subarray
12 let currentLCM = nums[start];
13
14 // Expand the subarray towards the right
15 for (let end = start; end < numElements; ++end) {
16 let nextElement = nums[end];
17
18 // Calculate the LCM of the current subarray
19 // Note: mathjs library function lcm is used for LCM calculation
20 currentLCM = Math.lcm(currentLCM, nextElement) as number;
21
22 // If the LCM is equal to `k`, increment the count
23 if (currentLCM === k) {
24 count++;
25 }
26 }
27 }
28
29 // Return the total count of subarrays whose LCM is `k`
30 return count;
31}
32How many ways can you arrange the three letters A, B and C?
Time and Space Complexity
The provided Python code calculates the number of contiguous subarrays in an array nums where the Least Common Multiple (LCM) of the subarray is equal to a given integer k. The code is a brute-force approach where it iterates through every possible subarray using nested loops.
Time Complexity
The time complexity of the code is determined by the nested loops and the computation of the LCM within the inner loop. There are O(n) possible starting points for a subarray (where n is the length of the array) and, for each start point, up to O(n) ending points. Therefore, we are considering O(n^2) contiguous subarrays.
Computing the LCM within the inner loop has a varying complexity depending on the implementation of the lcm function, which is not shown in the code snippet. Assuming the lcm function uses the Greatest Common Divisor (GCD) algorithm which, on average, has a time complexity of O(log(min(a, b))) where a and b are the input numbers, the overall time complexity of the inner loop is O(log(min(a, b))).
However, since the computation of the LCM is done in a successive manner, where each computed LCM is then used with the next array element, in the worst case, the numbers can grow exponentially with respect to their indices. But this behavior is still bounded by the small input bounds due to integer limits in a practical scenario, and the average case would often be much better.
Given these nested loops and assuming the average complexity for LCM computations, the overall time complexity can be considered O(n^2 * log(min(a, b))).
Space Complexity
The space complexity of the code is O(1) as there are only a few integer variables being used, and there is no additional space being allocated that grows with the input size. The variables n, ans, a, and x are used to track the length of the array, the result count, the running LCM of the current subarray, and the LCM of the current elements respectively.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.