JavaScript 计算数组范围内的乘积

我们将得到一个数组，并且需要回答一些与给定范围相关的查询，即从给定的起始索引到结束点或索引的范围内元素的乘积。我们将在本文中介绍一些使用JavaScript实现上述问题的方法，并附有解释。

问题介绍

我们被给定一个数组和一些查询，每个查询中我们将通过指定范围的第一个和最后一个索引来给出一些范围，我们需要回答该范围内每个元素的乘积。

例如 –

Given array: 1 2 3 4 5 6
the product of range 0 to 2 is: 1 * 2 * 3 = 6. 
The product of range 2 to 4 is: 3 * 4 * 5 = 60.

首先我们将看到两种解决问题的方法，一种是简单的原生方法，另一种是数学上的模反演方法。

原生方法

在这种方法中，我们将简单地遍历数组，并为每个查询维护一个变量来存储乘积。

示例

让我们看看代码−

// function to find the range’s product 
function rangeFun(arr, L, R){

   // getting length of the array 
   var len = arr.length

   // variable to maintain the result
   var ans = 1

   // traversing over the array in the given range 
   for(var i = L; i <= R; i++)    {
      ans *= arr[i];
   }
   console.log("The product of the elements in the given range " + L + " to " + R + " is: " + ans )
}
// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6]

// calling the function in the range 0 to 2
rangeFun(arr, 0 ,2)

// calling the function in range 3 to 5
rangeFun(arr, 3 , 5)

时间和空间复杂度

上述代码的时间复杂度是O(N)，其中N是给定数组中元素的数量，而空间复杂度是O(1)，因为我们没有使用任何额外的空间。

在上述代码中，时间复杂度仅为O(N)，但问题是它只适用于单个查询，当查询的数量增加时，它会以线性方式增加，这使得它无法处理N个查询。为了解决这个问题，我们将使用数学概念的模逆。

模乘逆

由于P是一个质数，我们可以利用模乘逆。我们可以使用动态规划计算在模P下的预乘数组，其中索引i处的值包含范围[0，i]内的乘积。类似地，我们可以确定相对于P的预逆乘积。现在每个查询可以在O(1)时间内回答。

由于乘积是在模P下计算的，所以我们不能计算解决方案作为Product[R]/Product[L-1]。如果我们不在模P下计算乘积，就会存在溢出的风险。

示例

让我们来看一下代码 –

// defining some variable to work with 
var max_length = 100;
var preProduct = new Array(max_length);
var inverseProduct = new Array(max_length);

// function to return the modulo inverse 
function modInverse(a, m){
   var m0 = m, t, q;
   var x0 = 0
   var x1 = 1
   if (m == 1)    {
      return 0;
   }
   while (a > 1)    {

      // here q is the quotient
      q = parseInt(a / m, 10);
      t = m;

      // m is remainder now, process

      // same as Euclid's algo
      m = a % m;
      a = t;
      t = x0;
      x0 = x1 - q * x0;
      x1 = t;
   }
   // Make x1 positive
   if (x1 < 0)    {
      x1 += m0;
   }
   return x1;
}

// calculating pre_product of the givne array
function calculate_Pre_Product(arr, n, p){
   preProduct[0] = arr[0];
   for (var i = 1; i < n; i++)    {
      preProduct[i] = preProduct[i - 1] * arr[i];
      preProduct[i] = preProduct[i] % p;
   }
}

// Calculating inverse_product of the given array 
function calculate_inverse_product(arr, n, p){
   inverseProduct[0] = modInverse(preProduct[0], p);
   for (var i = 1; i < n; i++) {
      inverseProduct[i] = modInverse(preProduct[i], p);
   }
}

// defining the function to calculate Product

// in the given range.
function rangeFun(arr, L, R, p){
   var ans = 0;
   if (L == 0) {
      ans = preProduct[R];
   }
   else{ 
      ans = preProduct[R] * inverseProduct[L - 1];
   }
   console.log("The product of the elements in the given range " + L + " to " + R + " is: " + ans )
}

// defining the array 
var arr = [ 1, 2, 3, 4, 5, 6 ];

// defining the modulo prime number
var p = 113;

// Calculating PreProduct and InverseProduct
calculate_Pre_Product(arr, arr.length, p);
calculate_inverse_product(arr, arr.length, p);
rangeFun(arr, 0 ,2, p)
rangeFun(arr, 0 , 5,  p)