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.

Problem Introduction

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.

Mathematical relationship between LCM and GCD

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.

Naive method

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 -

Example

// 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])
}

Time and space complexity

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 N², which makes this method inefficient. Let's see this is another way &miinus;

Line Segment Tree Method

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 -

Example

// 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 conclusion

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!