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