Programa Javascript para la media de rango en array

Dada una array de n enteros. Te dan q consultas. Escriba un programa para imprimir el valor mínimo de la media en el rango de l a r para cada consulta en una nueva línea.

Ejemplos: 

Input : arr[] = {1, 2, 3, 4, 5}
        q = 3
        0 2
        1 3
        0 4
Output : 2
         3
         3
Here for 0 to 2 (1 + 2 + 3) / 3 = 2

Input : arr[] = {6, 7, 8, 10}
        q = 2
        0 3
        1 2
Output : 7
         7

Enfoque ingenuo: podemos ejecutar un ciclo para cada consulta de l a r y encontrar la suma y el número de elementos en el rango. Después de esto, podemos imprimir el piso de la media para cada consulta.  

<script>
    // Javascript program to find floor value
    // of mean in range l to r
     
    // To find mean of range in l to r
    function findMean(arr, l, r)
    {
        // Both sum and count are
        // initialize to 0
        let sum = 0, count = 0;
    
        // To calculate sum and number
        // of elements in range l to r
        for (let i = l; i <= r; i++) {
            sum += arr[i];
            count++;
        }
    
        // Calculate floor value of mean
        let mean = Math.floor(sum / count);
    
        // Returns mean of array
        // in range l to r
        return mean;
    }
     
    let arr = [ 1, 2, 3, 4, 5 ];
    document.write(findMean(arr, 0, 2) + "</br>");
    document.write(findMean(arr, 1, 3) + "</br>");
    document.write(findMean(arr, 0, 4) + "</br>");
 
</script>

Producción : 

2
3
3

Complejidad temporal: O(n*q) donde q es el número de consultas y n es el tamaño de la array. Aquí, en el código anterior, q es 3 ya que la función findMean se usa 3 veces.
Espacio Auxiliar: O(1)

Enfoque eficiente: podemos encontrar la suma de números usando números usando el prefijo sum . El prefixSum[i] denota la suma de los primeros i elementos. Entonces, la suma de los números en el rango de l a r será prefixSum[r] – prefixSum[l-1]. El número de elementos en el rango de l a r será r – l + 1. Entonces ahora podemos imprimir la media del rango de l a r en O(1). 

<script>
 
// Javascript program to find floor value
// of mean in range l to r
let MAX = 1000005;
let prefixSum = new Array(MAX);
prefixSum.fill(0);
 
// To calculate prefixSum of array
function calculatePrefixSum(arr, n)
{
     
    // Calculate prefix sum of array
    prefixSum[0] = arr[0];
    for(let i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}
 
// To return floor of mean
// in range l to r
function findMean(l, r)
{
    if (l == 0)
       return parseInt(Math.floor(prefixSum[r] /
                      (r + 1)), 10);
      
    // Sum of elements in range l to
    // r is prefixSum[r] - prefixSum[l-1]
    // Number of elements in range
    // l to r is r - l + 1
    return parseInt(Math.floor((prefixSum[r] -
                                prefixSum[l - 1]) /
                                (r - l + 1)), 10);
}
 
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let n = arr.length;
calculatePrefixSum(arr, n);
 
document.write(findMean(1, 2) + "</br>");
document.write(findMean(1, 3) + "</br>");
document.write(findMean(1, 4) + "</br>");
 
// This code is contributed by divyeshrabadiya07
 
</script>

Producción: 

2
3
3

Complejidad temporal : O(n+q) donde q es el número de consultas y n es el tamaño de la array. Aquí, en el código anterior, q es 3 ya que la función findMean se usa 3 veces.
Espacio Auxiliar : O(k) donde k=1000005.

Consulte el artículo completo sobre la media del rango en una array para obtener más detalles.