Dada una array arr[] de tamaño N , la tarea es encontrar el promedio de los elementos de la array sin que se produzca un desbordamiento.
Ejemplos:
Entrada: arr[] = { INT_MAX, INT_MAX }
Salida:
Promedio por método estándar: -1.0000000000
Promedio por método eficiente: 2147483647.0000000000
Explicación:
El promedio de los dos números por método estándar es (suma / 2).
Dado que la suma de los dos números excede INT_MAX, la salida obtenida por el método estándar es incorrecta.Entrada: arr[] = { INT_MAX, 1, 2 }
Salida:
Promedio por método estándar: -715827882.0000000000
Promedio por método eficiente: 715827883.3333332539
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- El promedio de N elementos de la array se puede obtener dividiendo la suma de los elementos de la array por N. Pero calcular la suma de la array arr[] puede provocar un desbordamiento de enteros, si la array contiene números enteros grandes.
- Por lo tanto, el promedio de la array se puede calcular de manera eficiente mediante los siguientes pasos:
- Atraviesa la array usando una variable i sobre el rango de índices [0, N – 1]
- Actualizar promedio = (promedio+ (arr[i] – promedio)/(i+1))
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos sum como 0 y avg como 0 , para almacenar la suma y el promedio de los elementos de la array respectivamente.
- Recorra la array arr[], actualice avg = avg + (arr[i] – avg) / (i + 1) y actualice sum = sum + arr[i].
- Después de completar los pasos anteriores, imprima el promedio por el método estándar, es decir, sum/N e imprima el promedio por el método eficiente, es decir, avg
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate average of
// an array using standard method
double average(int arr[], int N)
{
// Stores the sum of array
int sum = 0;
// Find the sum of the array
for (int i = 0; i < N; i++)
sum += arr[i];
// Return the average
return (double)sum / N;
}
// Function to calculate average of
// an array using efficient method
double mean(int arr[], int N)
{
// Store the average of the array
double avg = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update avg
avg += (arr[i] - avg) / (i + 1);
}
// Return avg
return avg;
}
// Driver Code
int main()
{
// Input
int arr[] = { INT_MAX, 1, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Average by Standard method: " << fixed
<< setprecision(10) << average(arr, N) << endl;
cout << "Average by Efficient method: " << fixed
<< setprecision(10) << mean(arr, N) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate average of
// an array using standard method
static Double average(int arr[], int N)
{
// Stores the sum of array
int sum = 0;
// Find the sum of the array
for (int i = 0; i < N; i++)
sum += arr[i];
// Return the average
return Double.valueOf(sum / N);
}
// Function to calculate average of
// an array using efficient method
static Double mean(int arr[], int N)
{
// Store the average of the array
Double avg = 0.0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Update avg
avg += Double.valueOf((arr[i] - avg) / (i + 1));
}
// Return avg
return avg;
}
// Driver Code
public static void main(String args[])
{
// Input
int arr[] = {Integer.MAX_VALUE, 1, 2 };
int N = arr.length;
// Function call
System.out.println("Average by Standard method: "+ String.format("%.10f", average(arr, N)));
System.out.println("Average by Efficient method: "+ String.format("%.10f", mean(arr, N)));
}
}
// This code is contributed by ipg2016107.
Python3
# Python3 program for the above approach
import sys
# Function to calculate average of
# an array using standard method
def average(arr, N):
# Stores the sum of array
sum = 0
# Find the sum of the array
for i in range(N):
sum += arr[i]
# Return the average
return sum // N * 1.0 - 1
# Function to calculate average of
# an array using efficient method
def mean(arr, N):
# Store the average of the array
avg = 0
# Traverse the array arr[]
for i in range(N):
# Update avg
avg += (arr[i] - avg) / (i + 1)
# Return avg
return round(avg, 7)
# Driver Code
if __name__ == '__main__':
# Input
arr = [2147483647, 1, 2]
N = len(arr)
# Function call
print("Average by Standard method: ","{:.10f}".format(
-1.0 * average(arr, N)))
print("Average by Efficient method: ","{:.10f}".format(
mean(arr, N)))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate average of
// an array using standard method
static double average(int[] arr, int N)
{
// Stores the sum of array
int sum = 0;
// Find the sum of the array
for(int i = 0; i < N; i++)
sum += arr[i];
// Return the average
return (double)(sum / N);
}
// Function to calculate average of
// an array using efficient method
static double mean(int[] arr, int N)
{
// Store the average of the array
double avg = 0.0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update avg
avg += ((double)((arr[i] - avg) / (i + 1)));
}
// Return avg
return avg;
}
// Driver Code
static public void Main()
{
// Input
int[] arr = { Int32.MaxValue, 1, 2 };
int N = arr.Length;
// Function call
Console.WriteLine("Average by Standard method: " +
(average(arr, N)).ToString("F10"));
Console.WriteLine("Average by Efficient method: " +
(mean(arr, N)).ToString("F10"));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for the above approach
// Function to calculate average of
// an array using standard method
function average(arr, N)
{
// Stores the sum of array
var sum = 0;
// Find the sum of the array
for(var i = 0; i < N; i++)
sum += arr[i];
if(sum>2147483647)
{
sum = -2147483647 + (sum - 2147483649)
}
// Return the average
return parseInt(sum / N);
}
// Function to calculate average of
// an array using efficient method
function mean(arr, N)
{
// Store the average of the array
var avg = 0;
// Traverse the array arr[]
for(var i = 0; i < N; i++) {
// Update avg
avg += parseFloat((arr[i] - avg) / (i + 1));
}
// Return avg
return avg;
}
// Driver Code
// Input
var arr = [2147483647, 1, 2 ];
var N = arr.length
// Function call
document.write( "Average by Standard method: " + average(arr, N).toFixed(10) + "<br>");
document.write( "Average by Efficient method: " + mean(arr, N).toFixed(10)+ "<br>");
</script>
Producción:
Average by Standard method: -715827882.0000000000 Average by Efficient method: 715827883.3333332539
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por arun singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA