Dada una array arr[] que consta de N enteros, la tarea es encontrar la media de la array formada por los productos de pares no ordenados de la array dada.
Ejemplos:
Entrada: arr[] = {2, 5, 7}
Salida: 19.67
Explicación:
El producto de pares no ordenados de arreglo arr[] son 2 * 5 = 10, 2 * 7 = 14 y 5 * 7 = 35.
Por lo tanto, la resultante array de producto de pares es {10, 14, 35}.
La media de la array de producto de pares es 59/3 = 19,67Entrada: arr[] = {1, 2, 4, 8}
Salida: 11.67
Explicación:
El producto de pares no ordenados de array arr[] son 1 * 2 = 2, 1 * 4 = 4, 1 * 8 = 8, 2 * 4 = 8, 2 * 8 = 16, 4 * 8 = 32.
Por lo tanto, la array resultante del producto de pares es {2, 4, 8, 8, 16, 32}.
La media de la array de productos de pares es 70/6, es decir, 11,67
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles de array pairProductArray[] , es decir, una array formada por el producto de pares no ordenados de la array arr[] . Luego, encuentre la media de pairProductArray[] . Siga los pasos a continuación para resolver el problema:
- Genere todos los pares posibles de la array arr[] y almacene sus productos en pairProductArray[] .
- Inicialice una variable sum para almacenar la suma de los elementos de pairProductArray[] .
- Divide la variable sum con el tamaño de pairProductArray[] para obtener la media requerida.
- Finalmente, imprima el valor de la suma como la media resultante.
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 find the mean of pair
// product array of arr[]
float pairProductMean(int arr[], int N)
{
// Store product of pairs
vector<int> pairArray;
// Generate all unordered pairs
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
int pairProduct
= arr[i] * arr[j];
// Store product of pairs
pairArray.push_back(pairProduct);
}
}
// Size of pairArray
int length = pairArray.size();
// Store sum of pairArray
float sum = 0;
for (int i = 0; i < length; i++)
sum += pairArray[i];
// Stores the mean of pairArray[]
float mean;
// Find mean of pairArray[]
if (length != 0)
mean = sum / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 4, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << fixed << setprecision(2)
<< pairProductMean(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to find the mean
// of pair product array of arr[]
static double pairProductMean(int arr[],
int N)
{
// Store product of pairs
Vector<Integer> pairArray =
new Vector<>();
// Generate all unordered pairs
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
int pairProduct = arr[i] *
arr[j];
// Store product of pairs
pairArray.add(pairProduct);
}
}
// Size of pairArray
int length = pairArray.size();
// Store sum of pairArray
float sum = 0;
for (int i = 0; i < length; i++)
sum += pairArray.get(i);
// Stores the mean of
// pairArray[]
float mean;
// Find mean of pairArray[]
if (length != 0)
mean = sum / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = {1, 2, 4, 8};
int N = arr.length;
// Function Call
System.out.format("%.2f",
pairProductMean(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the
# above approach
# Function to find the mean
# of pair product array of arr
def pairProductMean(arr, N):
# Store product of pairs
pairArray = [];
# Generate all unordered
# pairs
for i in range(N):
for j in range(i + 1, N):
pairProduct = arr[i] * arr[j];
# Store product of pairs
pairArray.append(pairProduct);
# Size of pairArray
length = len(pairArray);
# Store sum of pairArray
sum = 0;
for i in range(length):
sum += pairArray[i];
# Stores the mean of
# pairArray
mean = 0;
# Find mean of pairArray
if (length != 0):
mean = sum / length;
else:
mean = 0;
# Return the resultant
# mean
return mean;
# Driver Code
if __name__ == '__main__':
# Given array arr
arr = [1, 2, 4, 8];
N = len(arr);
# Function Call
print("{0:.2f}".format(
pairProductMean(arr, N)))
# This code is contributed by Rajput-Ji
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the mean
// of pair product array of []arr
static double pairProductMean(int []arr,
int N)
{
// Store product of pairs
List<int> pairArray =
new List<int>();
// Generate all unordered pairs
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
int pairProduct = arr[i] *
arr[j];
// Store product of pairs
pairArray.Add(pairProduct);
}
}
// Size of pairArray
int length = pairArray.Count;
// Store sum of pairArray
float sum = 0;
for (int i = 0; i < length; i++)
sum += pairArray[i];
// Stores the mean of
// pairArray[]
float mean;
// Find mean of pairArray[]
if (length != 0)
mean = sum / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 2, 4, 8};
int N = arr.Length;
// Function Call
Console.WriteLine("{0:F2}",
pairProductMean(arr,
N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the
// above approach
// Function to find the mean
// of pair product array of arr
function pairProductMean(arr , N)
{
// Store product of pairs
var pairArray = [];
// Generate all unordered pairs
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
var pairProduct = arr[i] * arr[j];
// Store product of pairs
pairArray.push(pairProduct);
}
}
// Size of pairArray
var length = pairArray.length;
// Store sum of pairArray
var sum = 0;
for (i = 0; i < length; i++)
sum += pairArray[i];
// Stores the mean of
// pairArray
var mean;
// Find mean of pairArray
if (length != 0)
mean = sum / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
// Given array arr
var arr = [ 1, 2, 4, 8 ];
var N = arr.length;
// Function Call
document.write(pairProductMean(arr, N).toFixed(2));
// This code contributed by gauravrajput1
</script>
Producción
11.67
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: la idea es usar el hecho de que cada elemento arr[i] se multiplica con cada elemento arr[j] que está en el lado derecho del elemento arr[i] , más formalmente el elemento en el índice i se multiplica por todos los elementos posicionados en el índice j tales que j > i . Siga los pasos a continuación para resolver el problema:
- Cree una array de suma de sufijos suffixSumArray[] para la array dada arr[] .
- Inicialice la variable res para almacenar la suma de los pares de productos de la array arr[] .
- Iterar array arr[] y para cada posición i incrementar res con arr[i]*suffixSumArray[i+1] .
- Divide la variable res con N*(N – 1)/ 2 que es el número de productos posibles.
- Finalmente, imprima el valor de res como la media resultante.
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 find the mean of pair
// product array of arr[]
float pairProductMean(int arr[], int N)
{
// Initializing suffix sum array
int suffixSumArray[N];
suffixSumArray[N - 1] = arr[N - 1];
// Build suffix sum array
for (int i = N - 2; i >= 0; i--) {
suffixSumArray[i]
= suffixSumArray[i + 1]
+ arr[i];
}
// Size of pairProductArray
int length = (N * (N - 1)) / 2;
// Stores sum of pairProductArray
float res = 0;
for (int i = 0; i < N - 1; i++) {
res += arr[i]
* suffixSumArray[i + 1];
}
// Store the mean
float mean;
// Find mean of pairProductArray
if (length != 0)
mean = res / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 4, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << fixed << setprecision(2)
<< pairProductMean(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the mean of pair
// product array of arr[]
static float pairProductMean(int arr[], int N)
{
// Initializing suffix sum array
int suffixSumArray[] = new int[N];
suffixSumArray[N - 1] = arr[N - 1];
// Build suffix sum array
for(int i = N - 2; i >= 0; i--)
{
suffixSumArray[i] = suffixSumArray[i + 1] +
arr[i];
}
// Size of pairProductArray
int length = (N * (N - 1)) / 2;
// Stores sum of pairProductArray
float res = 0;
for(int i = 0; i < N - 1; i++)
{
res += arr[i] *
suffixSumArray[i + 1];
}
// Store the mean
float mean;
// Find mean of pairProductArray
if (length != 0)
mean = res / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 4, 8 };
int N = arr.length;
// Function call
System.out.format("%.2f",
pairProductMean(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the mean of pair # product array of arr[] def pairProductMean(arr, N): # Initializing suffix sum array suffixSumArray = [0] * N suffixSumArray[N - 1] = arr[N - 1] # Build suffix sum array for i in range(N - 2, -1, -1): suffixSumArray[i] = suffixSumArray[i + 1] + arr[i] # Size of pairProductArray length = (N * (N - 1)) // 2 # Stores sum of pairProductArray res = 0 for i in range(N - 1): res += arr[i] * suffixSumArray[i + 1] # Store the mean mean = 0 # Find mean of pairProductArray if (length != 0): mean = res / length else: mean = 0 # Return the resultant mean return mean # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 4, 8 ] N = len(arr) # Function Call print(round(pairProductMean(arr, N), 2)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the mean of pair
// product array of arr[]
static double pairProductMean(int[] arr, int N)
{
// Initializing suffix sum array
int[] suffixSumArray = new int[N];
suffixSumArray[N - 1] = arr[N - 1];
// Build suffix sum array
for(int i = N - 2; i >= 0; i--)
{
suffixSumArray[i] = suffixSumArray[i + 1] +
arr[i];
}
// Size of pairProductArray
int length = (N * (N - 1)) / 2;
// Stores sum of pairProductArray
double res = 0;
for(int i = 0; i < N - 1; i++)
{
res += arr[i] *
suffixSumArray[i + 1];
}
// Store the mean
double mean;
// Find mean of pairProductArray
if (length != 0)
mean = res / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver code
public static void Main()
{
// Given array arr[]
int[] arr = { 1, 2, 4, 8 };
int N = arr.Length;
// Function call
Console.WriteLine(string.Format("{0:0.00}",
pairProductMean(arr, N)));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program for the above approach
// Function to find the mean of pair
// product array of arr[]
function pairProductMean(arr, N)
{
// Initializing suffix sum array
var suffixSumArray = Array(N);
suffixSumArray[N - 1] = arr[N - 1];
// Build suffix sum array
for (var i = N - 2; i >= 0; i--) {
suffixSumArray[i]
= suffixSumArray[i + 1]
+ arr[i];
}
// Size of pairProductArray
var length = (N * (N - 1)) / 2;
// Stores sum of pairProductArray
var res = 0;
for (var i = 0; i < N - 1; i++) {
res += arr[i]
* suffixSumArray[i + 1];
}
// Store the mean
var mean;
// Find mean of pairProductArray
if (length != 0)
mean = res / length;
else
mean = 0;
// Return the resultant mean
return mean;
}
// Driver Code
// Given array arr[]
var arr = [ 1, 2, 4, 8 ];
var N = arr.length;
// Function Call
document.write( pairProductMean(arr, N).toFixed(2));
</script>
Producción
11.67
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA