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.  

C++

// CPP program to find floor value
// of mean in range l to r
#include <bits/stdc++.h>
using namespace std;
 
// To find mean of range in l to r
int findMean(int arr[], int l, int r)
{
    // Both sum and count are
    // initialize to 0
    int sum = 0, count = 0;
 
    // To calculate sum and number
    // of elements in range l to r
    for (int i = l; i <= r; i++) {
        sum += arr[i];
        count++;
    }
 
    // Calculate floor value of mean
    int mean = floor(sum / count);
 
    // Returns mean of array
    // in range l to r
    return mean;
}
 
// Driver program to test findMean()
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    cout << findMean(arr, 0, 2) << endl;
    cout << findMean(arr, 1, 3) << endl;
    cout << findMean(arr, 0, 4) << endl;
    return 0;
}

C

// C program to find floor value
// of mean in range l to r
#include <stdio.h>
#include <math.h>
 
// To find mean of range in l to r
int findMean(int arr[], int l, int r)
{
    // Both sum and count are
    // initialize to 0
    int sum = 0, count = 0;
 
    // To calculate sum and number
    // of elements in range l to r
    for (int i = l; i <= r; i++) {
        sum += arr[i];
        count++;
    }
 
    // Calculate floor value of mean
    int mean = floor(sum / count);
 
    // Returns mean of array
    // in range l to r
    return mean;
}
 
// Driver program to test findMean()
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    printf("%d\n",findMean(arr, 0, 2));
    printf("%d\n",findMean(arr, 1, 3));
    printf("%d\n",findMean(arr, 0, 4));
    return 0;
}
 
// This code is contributed by kothavvsaakash

Java

// Java program to find floor value
// of mean in range l to r
public class Main {
 
    // To find mean of range in l to r
    static int findMean(int arr[], int l, int r)
    {
        // Both sum and count are
        // initialize to 0
        int sum = 0, count = 0;
 
        // To calculate sum and number
        // of elements in range l to r
        for (int i = l; i <= r; i++) {
            sum += arr[i];
            count++;
        }
 
        // Calculate floor value of mean
        int mean = (int)Math.floor(sum / count);
 
        // Returns mean of array
        // in range l to r
        return mean;
    }
 
    // Driver program to test findMean()
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        System.out.println(findMean(arr, 0, 2));
        System.out.println(findMean(arr, 1, 3));
        System.out.println(findMean(arr, 0, 4));
    }
}

Python3

# Python 3 program to find floor value
# of mean in range l to r
import math
 
# To find mean of range in l to r
def findMean(arr, l, r):
     
    # Both sum and count are
    # initialize to 0
    sum, count = 0, 0
     
    # To calculate sum and number
    # of elements in range l to r
    for i in range(l, r + 1):
        sum += arr[i]
        count += 1
 
    # Calculate floor value of mean
    mean = math.floor(sum / count)
 
    # Returns mean of array
    # in range l to r
    return mean
 
# Driver Code
arr = [ 1, 2, 3, 4, 5 ]
     
print(findMean(arr, 0, 2))
print(findMean(arr, 1, 3))
print(findMean(arr, 0, 4))
 
# This code is contributed
# by PrinciRaj1992

C#

//C# program to find floor value
// of mean in range l to r
using System;
 
public class GFG {
  
    // To find mean of range in l to r
    static int findMean(int []arr, int l, int r)
    {
        // Both sum and count are
        // initialize to 0
        int sum = 0, count = 0;
  
        // To calculate sum and number
        // of elements in range l to r
        for (int i = l; i <= r; i++) {
            sum += arr[i];
            count++;
        }
  
        // Calculate floor value of mean
        int mean = (int)Math.Floor((double)sum / count);
  
        // Returns mean of array
        // in range l to r
        return mean;
    }
  
    // Driver program to test findMean()
    public static void Main()
    {
        int []arr = { 1, 2, 3, 4, 5 };
        Console.WriteLine(findMean(arr, 0, 2));
        Console.WriteLine(findMean(arr, 1, 3));
        Console.WriteLine(findMean(arr, 0, 4));
    }
}
 
/*This code is contributed by PrinciRaj1992*/

PHP

<?php
// PHP 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
    $sum = 0;
    $count = 0;
 
    // To calculate sum and
    // number of elements in
    // range l to r
    for ($i = $l; $i <= $r; $i++)
    {
        $sum += $arr[$i];
        $count++;
    }
 
    // Calculate floor
    // value of mean
    $mean = floor($sum / $count);
 
    // Returns mean of array
    // in range l to r
    return $mean;
}
 
// Driver Code
$arr = array(1, 2, 3, 4, 5);
echo findMean($arr, 0, 2), "\n";
echo findMean($arr, 1, 3), "\n";
echo findMean($arr, 0, 4), "\n";
 
// This code is contributed by ajit
?>

Javascript

<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). 

C++

// CPP program to find floor value
// of mean in range l to r
#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
 
int prefixSum[MAX];
 
// To calculate prefixSum of array
void calculatePrefixSum(int arr[], int n)
{
    // Calculate prefix sum of array
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}
 
// To return floor of mean
// in range l to r
int findMean(int l, int r)
{
    if (l == 0)
      return floor(prefixSum[r]/(r+1));
 
    // 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 floor((prefixSum[r] -
          prefixSum[l - 1]) / (r - l + 1));
}
 
// Driver program to test above functions
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    calculatePrefixSum(arr, n);
    cout << findMean(0, 2) << endl;
    cout << findMean(1, 3) << endl;
    cout << findMean(0, 4) << endl;
    return 0;
}

Java

// Java program to find floor value
// of mean in range l to r
public class Main {
public static final int MAX = 1000005;
    static int prefixSum[] = new int[MAX];
 
    // To calculate prefixSum of array
    static void calculatePrefixSum(int arr[], int n)
    {
        // Calculate prefix sum of array
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
 
    // To return floor of mean
    // in range l to r
    static int findMean(int l, int r)
    {
        if (l == 0)
           return (int)Math.floor(prefixSum[r] / (r + 1));
         
        // 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 (int)Math.floor((prefixSum[r] -
                prefixSum[l - 1]) / (r - l + 1));
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
        calculatePrefixSum(arr, n);
        System.out.println(findMean(1, 2));
        System.out.println(findMean(1, 3));
        System.out.println(findMean(1, 4));
    }
}

Python3

# Python3 program to find floor value
# of mean in range l to r
import math as mt
 
MAX = 1000005
prefixSum = [0 for i in range(MAX)]
 
# To calculate prefixSum of array
def calculatePrefixSum(arr, n):
 
    # Calculate prefix sum of array
    prefixSum[0] = arr[0]
 
    for i in range(1,n):
        prefixSum[i] = prefixSum[i - 1] + arr[i]
 
# To return floor of mean
# in range l to r
def findMean(l, r):
 
    if (l == 0):
        return mt.floor(prefixSum[r] / (r + 1))
 
    # 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 (mt.floor((prefixSum[r] -
                      prefixSum[l - 1]) /
                          (r - l + 1)))
 
# Driver Code
arr = [1, 2, 3, 4, 5]
 
n = len(arr)
 
calculatePrefixSum(arr, n)
print(findMean(0, 2))
print(findMean(1, 3))
print(findMean(0, 4))
 
# This code is contributed by Mohit Kumar

C#

// C# program to find floor value
// of mean in range l to r
using System;
                     
public class GFG {
public static readonly int MAX = 1000005;
    static int []prefixSum = new int[MAX];
  
    // To calculate prefixSum of array
    static void calculatePrefixSum(int []arr, int n)
    {
        // Calculate prefix sum of array
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
  
    // To return floor of mean
    // in range l to r
    static int findMean(int l, int r)
    {
        if (l == 0)
           return (int)Math.Floor((double)(prefixSum[r] / (r + 1)));
          
        // 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 (int)Math.Floor((double)(prefixSum[r] -
                prefixSum[l - 1]) / (r - l + 1));
    }
  
    // Driver program to test above functions
    public static void Main()
    {
        int []arr = { 1, 2, 3, 4, 5 };
        int n = arr.Length;
        calculatePrefixSum(arr, n);
        Console.WriteLine(findMean(1, 2));
        Console.WriteLine(findMean(1, 3));
        Console.WriteLine(findMean(1, 4));
    }
}
 
//This code is contributed by PrinciRaj1992

Javascript

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

C

// C program to find floor value
// of mean in range l to r
#include <stdio.h>
#include <math.h>
 
#define MAX 1000005
 
int prefixSum[MAX];
 
// To calculate prefixSum of array
void calculatePrefixSum(int arr[], int n)
{
    // Calculate prefix sum of array
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i - 1] + arr[i];
}
 
// To return floor of mean
// in range l to r
int findMean(int l, int r)
{
    if (l == 0)
      return floor(prefixSum[r]/(r+1));
 
    // 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 floor((prefixSum[r] -
          prefixSum[l - 1]) / (r - l + 1));
}
 
// Driver program to test above functions
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    calculatePrefixSum(arr, n);
    printf("%d\n",findMean(0, 2));
    printf("%d\n",findMean(1, 3));
    printf("%d\n",findMean(0, 4));
    return 0;
}

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.

Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *