2470. Number of Subarrays With LCM Equal to K
Explanation
To solve this problem, we will iterate through all subarrays of the given array and calculate the least common multiple (LCM) of each subarray. We will then count the number of subarrays where the LCM is equal to the given integer k.
Algorithm:
- Initialize a count variable to store the number of subarrays with LCM equal to k.
- Iterate through all subarrays using two nested loops.
- For each subarray, calculate the LCM of its elements.
- If the LCM equals k, increment the count variable.
- Return the count as the final result.
Time Complexity:
- O(n^3) where n is the length of the input array nums. This is because we iterate through all subarrays and calculate the LCM for each subarray.
Space Complexity:
- O(1) as we are using constant extra space.
class Solution {
public int countSubarrays(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int lcm = calculateLCM(Arrays.copyOfRange(nums, i, j + 1));
if (lcm == k) {
count++;
}
}
}
return count;
}
private int calculateLCM(int[] arr) {
int lcm = arr[0];
for (int i = 1; i < arr.length; i++) {
lcm = lcm * arr[i] / gcd(lcm, arr[i]);
}
return lcm;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.