Given an array arr[] of length N, the task is to find the number of subarrays where the least common multiple (LCM) of the subarray is equal to K and the size of that subarray is S.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 6, S = 2
Output: 1
Explanation: {1, 2, 3 }, {2, 3}, {6}
There are 3 subarrays that can be generated from the main array with each having its LCM as 6. Out of which only {2, 3} is the length of 2.Input: arr[] = {3, 6, 2, 8, 4}, K = 6, S = 2
Output: 2
Explanation: {3, 6}, {6, 2}
There are only 2 subarrays having LCM as 6 and length as 2.
Approach: Implement the idea below to solve the problem
Maintain two loops, so as to calculate LCM starting from each index of arr[]. When the LCM get’s equal to K, check the length of the subarray.
Steps were taken to solve the problem:
- Initialize count = 0, to count the number of subarrays.
- Maintain a loop to iterate through each index of array arr[].
- Initialize LCM = arr[i], then again start a loop from that index to the end of array arr[].
- Find the LCM of the lcm calculated till now for the current subarray and arr[j] as LCM =( a * b ) / GCD(a, b).
- When LCM gets equal to given K and the size of the subarray is equal to S, increment in count variable by 1.
- Whenever LCM gets greater than k, Break the inner loop. As the LCM is going to increase or stay same, it is never going to decrease.
- Initialize LCM = arr[i], then again start a loop from that index to the end of array arr[].
Below is the implementation of the above approach.
C++
// Code to implement the approach #include <bits/stdc++.h> using namespace std; // Calculate LCM between a and b int LCM( int a, int b) { long prod = a * b; return prod / __gcd(a, b); } // Function to calculate number of subarrays // where LCM is equal to k and // size of subarray is S int subarrayEqualsLCMSize( int arr[], int k, int S, int N) { // Initialize variable to store number of subarrays int count = 0; // Generating all subarrays for ( int i = 0; i < N; i++) { int lcm = arr[i]; for ( int j = i; j < N; j++) { // Function call to calculate lcm lcm = LCM(lcm, arr[j]); // Check the conditions given if (lcm == k && j - i + 1 == S) count++; // If LCM becomes larger than k, // break as LCM is never going to // decrease if (lcm > k) break ; } } // Return the count of subarrays return count; } // Driver Code int main() { int arr[] = { 3, 2, 6, 8, 4 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 6, S = 2; // Function call cout << subarrayEqualsLCMSize(arr, K, S, N); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to calculate GCD static int gcd( int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Calculate LCM between a and b static int LCM( int a, int b) { int prod = a * b; return prod / gcd(a, b); } // Function to calculate number of subarrays // where LCM is equal to k and // size of subarray is S static int subarrayEqualsLCMSize( int [] arr, int k, int S, int N) { // Initialize variable to store number of subarrays int count = 0 ; // Generating all subarrays for ( int i = 0 ; i < N; i++) { int lcm = arr[i]; for ( int j = i; j < N; j++) { // Function call to calculate lcm lcm = LCM(lcm, arr[j]); // Check the conditions given if (lcm == k && j - i + 1 == S) { count++; } // If LCM becomes larger than k, // break as LCM is never going to // decrease if (lcm > k) { break ; } } } // Return the count of subarrays return count; } public static void main(String[] args) { int [] arr = { 3 , 2 , 6 , 8 , 4 }; int N = arr.length; int K = 6 , S = 2 ; // Function call System.out.print( subarrayEqualsLCMSize(arr, K, S, N)); } } |
Python
# Python code to implement the approach # Function to calculate GCD def gcd(a, b): if (b = = 0 ): return a return gcd(b, a % b) # Calculate LCM between a and b def LCM(a, b): prod = a * b return prod / gcd(a, b) # Function to calculate number of subarrays # where LCM is equal to k and # size of subarray is S def subarrayEqualsLCMSize(arr, k, S, N): # Initialize variable to store number of subarrays count = 0 # Generating all subarrays for i in range ( 0 , N): lcm = arr[i] for j in range (i, N): # Function call to calculate lcm lcm = LCM(lcm, arr[j]) # Check the conditions given if (lcm = = k and j - i + 1 = = S): count + = 1 # If LCM becomes larger than k, # break as LCM is never going to # decrease if (lcm > k): break # Return the count of subarrays return count # Driver Code arr = [ 3 , 2 , 6 , 8 , 4 ] N = len (arr) K = 6 S = 2 # Function call print (subarrayEqualsLCMSize(arr, K, S, N)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# implementation using System; public class GFG { static int GCD( int num1, int num2) { int Remainder; while (num2 != 0) { Remainder = num1 % num2; num1 = num2; num2 = Remainder; } return num1; } // Calculate LCM between a and b public static int LCM( int a, int b) { long prod = a * b; return ( int )(prod / GCD(a, b)); } // Function to calculate number of subarrays // where LCM is equal to k and // size of subarray is S public static int subarrayEqualsLCMSize( int [] arr, int k, int S, int N) { // Initialize variable to store number of subarrays int count = 0; // Generating all subarrays for ( int i = 0; i < N; i++) { int lcm = arr[i]; for ( int j = i; j < N; j++) { // Function call to calculate lcm lcm = LCM(lcm, arr[j]); // Check the conditions given if (lcm == k && j - i + 1 == S) count++; // If LCM becomes larger than k, // break as LCM is never going to // decrease if (lcm > k) break ; } } // Return the count of subarrays return count; } static public void Main() { int [] arr = { 3, 2, 6, 8, 4 }; int N = arr.Length; int K = 6, S = 2; // Function call Console.WriteLine( subarrayEqualsLCMSize(arr, K, S, N)); } } // This code is contributed by ksam24000 |
Javascript
function GCD(num1, num2) { let Remainder; while (num2 != 0) { Remainder = num1 % num2; num1 = num2; num2 = Remainder; } return num1; } // Calculate LCM between a and b function LCM( a, b) { let prod = a * b; return Math.floor(prod / GCD(a, b)); } // Function to calculate number of subarrays // where LCM is equal to k and // size of subarray is S function subarrayEqualsLCMSize(arr, k, S, N) { // Initialize variable to store number of subarrays let count = 0; // Generating all subarrays for (let i = 0; i < N; i++) { let lcm = arr[i]; for (let j = i; j < N; j++) { // Function call to calculate lcm lcm = LCM(lcm, arr[j]); // Check the conditions given if (lcm == k && j - i + 1 == S) count++; // If LCM becomes larger than k, // break as LCM is never going to // decrease if (lcm > k) break ; } } // Return the count of subarrays return count; } let arr = [ 3, 2, 6, 8, 4 ]; let N = arr.length; let K = 6, S = 2; // Function call console.log(subarrayEqualsLCMSize(arr, K, S, N)); // This code is contributed by akashish__ |
2
Time Complexity: O(N2 * Log N)
Auxiliary Space: O(1)
Related Articles:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Program to find LCM of two numbers
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!