Home > Article > Web Front-end > JavaScript program for range LCM queries
LCM stands for Least Common Multiple, the LCM of a set of numbers is the smallest number among all numbers that is divisible by all the numbers present in the given set. We will see the complete code along with the explanation of the given problem. In this article, we will implement a JavaScript program for a series of LCM queries.
In this problem, we are given an array containing integers and another array query containing pairs of numbers representing a given array range, and we have to calculate the LCM of all elements in that given range. For example -
If the given array is: [1, 2, 3, 4, 5, 6] and the query array is: [[1,3], [2,5]], then the first query element is [2, 3, 4] and 12 are LCM.
For the second query element is [3, 4, 5, 6] the LCM is 60.
To find the GCD we have a Euclidean formula with the help of which we can find the GCD of two numbers of logarithmic complexity and there is such a relationship between LCM and GCD -
LCM and GCD of a given set A {a1, a2, a3 …. , an} is: LCM(A) * GCD(A) = (a1 * a2 * a3* … * an) OR LCM(A) = (a1 * a2 * a3 … * an) / GCD(A)
So, we will find the GCD and product of all numbers and then from there, we can find the LCM of that number in O(1) operation.
The simplest way is to iterate over the array of queries and find the product of the elements in the given range and GCD for each query. Find the LCM from these two values and return it. Let's implement it in code -
// function to find the gcd of the given number function gcd(a,b){ if (a == 0) { return b; } else { return gcd(b%a,a); } } // function to find the lcm function lcmRange(arr, l, r){ // taking gcd as zero because gcd of 0 with any number is that same number var cur_gcd = 0 var product = 1 var cur_lcm = arr[l] for(var i = l+1 ;i <= r; i++) { product = cur_lcm * arr[i]; cur_gcd = gcd(cur_lcm, arr[i]) cur_lcm = product/cur_gcd } console.log("The LCM of the element in the given range from " + l + " to " + r + " is: " + cur_lcm); } // defining the array var arr = [ 1, 2, 3, 4, 5, 6] // defining the queries array var queries = [[1,3], [2,5]] // traversing over the array for(var i = 0; i< queries.length; i++){ lcmRange(arr,queries[i][0], queries[i][1]) }
The time complexity of the above code is O(Q*N*log(D)), where Q is the number of queries, N is the number of elements in the array, and D is the maximum number of arrays present in the array.
The space complexity of the above code is O(1) because we are not using any extra space.
In the above program, if the number of queries is equal to N, then its time complexity will be greater than N2, which makes this method inefficient. Let's see this is another way &miinus;
A line segment tree is a high-level data structure used to divide a problem into multiple line segments and then connect them in a power of 2 form. This requires some space for range queries and produces results in logarithmic time. Let's see its code -
// defining maximum size var MAX = 1000 // makking tree var tree = new Array(4*MAX); // declaring new array var arr = new Array(MAX); // function for lcm function lcm(a, b){ return a*b/gcd(a,b); } // function for gcd function gcd(a, b){ if (a == 0) { return b } else{ return gcd(b%a,a); } } // Function to creata a segment tree function build(first, last, cur_node){ // base condition if (first == last){ tree[cur_node] = arr[first]; return; } var mid = (first + last)/2 mid = Math.floor(mid); // creating left and right segments build(first, mid, 2*cur_node); build(mid+1, last, 2*cur_node + 1); // build the parent for current var lcm_l = tree[2*cur_node]; var lcm_r = tree[2*cur_node+1]; tree[cur_node] = lcm(lcm_l, lcm_r); } // Function to make queries for array range function query(first, last, l, r, cur_node){ // section out of current range // 1 is safe to return if (last < l || first > r){ return 1; } // complete inside the current segment if (l <= first && r >= last) return tree[cur_node]; // partially inside the current segment var mid = (first+last)/2; mid = Math.floor(mid) var lcm_l = query(first, mid, l, r, 2*cur_node); var lcm_r = query(mid+1, last, l, r, 2*cur_node+1); return lcm(lcm_l, lcm_r); } // defining the array arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 4; arr[4] = 5; arr[5] = 6; // build the segment tree build(0, 5, 1); // defining query array var queries = [[1,3], [2,5]] // traversing over the array for(var i = 0; i< queries.length; i++){ console.log("The LCM of the element in the given range from " + queries[i][0] + " to " + queries[i][1] + " is: " + query(0,5,queries[i][0],queries[i][1],1) ); }
In this tutorial, we implemented a JavaScript article to find range lcm query. We have seen two methods, one is the naive method with time complexity O(Q*N*log(D)), and the other is the line segment tree with time complexity O(Q*log(N)) accomplish. p>
The above is the detailed content of JavaScript program for range LCM queries. For more information, please follow other related articles on the PHP Chinese website!