JavaScript-Programm für Bereichs-LCM-Abfragen

LCM steht für kleinstes gemeinsames Vielfaches. Das LCM einer Zahlenmenge ist die kleinste Zahl unter allen Zahlen, die durch alle in der gegebenen Menge vorhandenen Zahlen teilbar ist. Wir werden den vollständigen Code zusammen mit der Erklärung des gegebenen Problems sehen. In diesem Artikel implementieren wir ein JavaScript-Programm für eine Reihe von LCM-Abfragen.

Einführung in das Problem

In diesem Problem erhalten wir ein Array mit ganzen Zahlen und eine weitere Array-Abfrage mit Zahlenpaaren, die einen bestimmten Array-Bereich darstellen, und wir müssen den LCM aller Elemente in diesem bestimmten Bereich berechnen. Zum Beispiel -

Wenn das gegebene Array: [1, 2, 3, 4, 5, 6] und das Abfragearray: [[1,3], [2,5]] ist, dann ist das erste Abfrageelement [2, 3 , 4] und 12 sind LCM.

Für das zweite Abfrageelement ist [3, 4, 5, 6] der LCM 60.

Mathematische Beziehung zwischen LCM und GCD

Um den GCD zu finden, haben wir eine euklidische Formel, mit deren Hilfe wir den GCD von zwei Zahlen logarithmischer Komplexität finden können, und es gibt eine solche Beziehung zwischen LCM und 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)

Wir ermitteln also den GCD und das Produkt aller Zahlen und können von dort aus den LCM dieser Zahl in der O(1)-Operation ermitteln.

Naive Methode

Der einfachste Weg besteht darin, das Array von Abfragen zu durchlaufen und das Produkt der Elemente im angegebenen Bereich und GCD für jede Abfrage zu ermitteln. Finden Sie den LCM aus diesen beiden Werten und geben Sie ihn zurück. Lassen Sie es uns im Code implementieren -

Beispiel

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(Q*N*log(D)), wobei Q die Anzahl der Abfragen, N die Anzahl der Elemente im Array und D die maximale Anzahl der im Array vorhandenen Arrays ist Array.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Wenn im obigen Programm die Anzahl der Abfragen gleich N ist, ist die zeitliche Komplexität größer als N², was diese Methode ineffizient macht. Mal sehen, das ist ein anderer Weg &miinus;

Liniensegmentbaummethode

Ein Segmentbaum ist eine Datenstruktur auf hoher Ebene, die dazu dient, ein Problem in Segmente zu unterteilen und diese dann in Zweierpotenzen zu verbinden. Dies erfordert etwas Platz für Bereichsabfragen und liefert Ergebnisse in logarithmischer Zeit. Sehen wir uns den Code an -

Beispiel

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

Fazit

In diesem Tutorial haben wir einen JavaScript-Artikel implementiert, um Bereichs-LCM-Abfragen zu finden. Wir haben zwei Methoden gesehen: Eine ist die naive Methode mit der Zeitkomplexität O(Q*N*log(D)) und die andere ist der Liniensegmentbaum mit der Zeitkomplexität O(Q*log(N)). p>

Das obige ist der detaillierte Inhalt vonJavaScript-Programm für Bereichs-LCM-Abfragen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!