Suma del producto de todos los pares de elementos de array

Dada una array A[] de enteros, encuentre la suma del producto de todos los pares de elementos de la array, es decir, necesitamos encontrar el producto después de la ejecución del siguiente pseudocódigo 

product = 0
for i = 1:n
    for j = i+1:n
        product = product + A[i]*A[j]

Ejemplos: 

Input : A[] = {1, 3, 4}
Output : 19
Possible Pairs : (1,3), (1,4), (3,4)
Sum of Product : 1*3 + 1*4 + 3*4 = 19

Solución ingenua:

Para cada índice i hacemos un bucle a través de j=i+1 a j=n y agregamos A[i]*A[j] cada vez. A continuación se muestra la implementación de la misma. 
 

// A naive C++ program to find sum of product
#include <iostream>
using namespace std;
 
// Returns sum of pair products
int findProductSum(int A[], int n)
{
    int product = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            product = product + A[i]*A[j];
    return product;
}
 
// Driver code
int main()
{
    int A[] = {1, 3, 4};
    int n = sizeof(A)/sizeof(A[0]);
 
    cout << "sum of product of all pairs "
    "of array elements : " << findProductSum(A, n);
 
    return 0;
}

/*package whatever //do not write package name here */
// A naive Java program to find sum of product
import java.io.*;
class test
{
    // Returns sum of pair products
    int findProductSum(int A[], int n)
    {
    int product = 0;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            product = product + A[i]*A[j];
    return product;
    }
}
class GFG {
 
// Driver code
    public static void main (String[] args) {
 
    int A[] = {1, 3, 4};
    int n = A.length;
    test t = new test();
    System.out.print("sum of product of all pairs of array elements : ");
    System.out.println(t.findProductSum(A, n));
 
    }
}

# A naive python3 program to find sum of product
  
# Returns sum of pair products
def findProductSum(A,n):
 
    product = 0
    for i in range (n):
        for j in range ( i+1,n):
            product = product + A[i]*A[j]
    return product
  
# Driver code
if __name__=="__main__":
 
    A = [1, 3, 4]
    n = len (A)
  
    print("sum of product of all pairs "
    "of array elements : " ,findProductSum(A, n))

// A naive C# program to find sum of product
using System;
 
class GFG
{
     
// Returns sum of pair products
static int findProductSum(int[] A, int n)
{
    int product = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            product = product + A[i] * A[j];
    return product;
}
 
// Driver code
public static void Main()
{
    int[] A = {1, 3, 4};
    int n = A.Length;
    Console.WriteLine("sum of product of all " +
                      "pairs of array elements : ");
    Console.WriteLine(findProductSum(A, n));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// A naive PHP program to find
// sum of product
 
// Returns sum of pair products
function findProductSum($A, $n)
{
    $product = 0;
    for ($i = 0; $i < $n; $i++)
        for ($j = $i + 1; $j < $n; $j++)
            $product = $product + $A[$i] * $A[$j];
    return $product;
}
 
    // Driver code
    $A = array (1, 3, 4);
    $n = sizeof($A);
 
    echo "sum of product of all pairs ",
         "of array elements : "
         ,findProductSum($A, $n);
 
// This code is contributed by aj_36
?>

<script>
 
// A naive Javascript program to find sum of product
   
// Returns sum of pair products
function findProductSum(A, n)
{
    let product = 0;
    for (let i= 0; i < n; i++)
        for (let j = i+1; j < n; j++)
            product = product + A[i]*A[j];
    return product;
}
   
// Driver code
    let A = [1, 3, 4];
    let n = A.length;
   
    document.write("sum of product of all pairs " +
    "of array elements : " + findProductSum(A, n));
     
// This code is contributed by Mayank Tyagi
   
</script>

Producción: 

sum of product of all pairs of array elements : 19

Complejidad de tiempo: O(n ² ) 
Complejidad de espacio: O(1)
 

Solución eficiente de O(n):

We know that
(a + b + c)2 = a2 + b2 + c2 + 2*(a*b + b*c + c*a)
Let required sum be P
Let E = (a1 + a2 + a3 + a4 ... + an)^2 
=> E = a12 + a22 + ... + an2 + 2*(a1*a2 + a1*a3 + ....)
=> E = a12 + a22 + ... + an2 + 2*(P)
=> P = ( E - (a12 + a22 + .... + an2) ) / 2

// Efficient C++ program to find sum pair products
// in an array.
#include <iostream>
using namespace std;
 
// required function
int findProductSum(int A[], int n)
{
    // calculating array sum (a1 + a2  ... + an)
    int array_sum = 0;
    for (int i = 0; i < n; i++)
        array_sum = array_sum + A[i];
 
    // calculating square of array sum
    // (a1 + a2 + ... + an)^2
    int array_sum_square = array_sum * array_sum;
 
    // calculating a1^2 + a2^2 + ... + an^2
    int individual_square_sum = 0;
    for (int i = 0; i < n; i++)
        individual_square_sum += A[i]*A[i];
 
    // required sum is (array_sum_square -
    // individual_square_sum) / 2
    return (array_sum_square - individual_square_sum)/2;
}
 
// Driver code
int main()
{
    int A[] = {1, 3, 4};
    int n = sizeof(A)/sizeof(A[0]);
    cout << "sum of product of all pairs of array "
            "elements : " << findProductSum(A, n);
    return 0;
}

// Efficient Java program to find sum pair products
// in an array.
class GFG
{
 
// required function
static int findProductSum(int A[], int n)
{
    // calculating array sum (a1 + a2 ... + an)
    int array_sum = 0;
    for (int i = 0; i < n; i++)
        array_sum = array_sum + A[i];
 
    // calculating square of array sum
    // (a1 + a2 + ... + an)^2
    int array_sum_square = array_sum * array_sum;
 
    // calculating a1^2 + a2^2 + ... + an^2
    int individual_square_sum = 0;
    for (int i = 0; i < n; i++)
        individual_square_sum += A[i] * A[i];
 
    // required sum is (array_sum_square -
    // individual_square_sum) / 2
    return (array_sum_square - individual_square_sum) / 2;
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = {1, 3, 4};
    int n = A.length;
    System.out.println("sum of product of all pairs of array "
            +"elements : " + findProductSum(A, n));
    }
}
 
// This code is contributed by 29AjayKumar

# Efficient python 3 program to find sum
# pair products in an array.
 
# required function
def findProductSum(A, n):
     
    # calculating array sum (a1 + a2 ... + an)
    array_sum = 0
    for i in range(0, n, 1):
        array_sum = array_sum + A[i]
 
    # calculating square of array sum
    # (a1 + a2 + ... + an)^2
    array_sum_square = array_sum * array_sum
 
    # calculating a1^2 + a2^2 + ... + an^2
    individual_square_sum = 0
    for i in range(0, n, 1):
        individual_square_sum += A[i] * A[i]
 
    # required sum is (array_sum_square -
    # individual_square_sum) / 2
    return (array_sum_square -
            individual_square_sum) / 2
 
# Driver code
if __name__ == '__main__':
    A = [1, 3, 4]
    n = len(A)
    print("sum of product of all pairs of",
          "array elements :", int(findProductSum(A, n)))
     
# This code is contributed by
# Sahil_Shelangia

// Efficient C# program to find sum pair
// products in an array.
using System;
 
class GFG
{
 
// required function
static int findProductSum(int[] A, int n)
{
    // calculating array sum (a1 + a2 ... + an)
    int array_sum = 0;
    for (int i = 0; i < n; i++)
        array_sum = array_sum + A[i];
 
    // calculating square of array sum
    // (a1 + a2 + ... + an)^2
    int array_sum_square = array_sum * array_sum;
 
    // calculating a1^2 + a2^2 + ... + an^2
    int individual_square_sum = 0;
    for (int i = 0; i < n; i++)
        individual_square_sum += A[i] * A[i];
 
    // required sum is (array_sum_square -
    // individual_square_sum) / 2
    return (array_sum_square -
            individual_square_sum) / 2;
}
 
// Driver code
public static void Main()
{
    int[] A = {1, 3, 4};
    int n = A.Length;
    Console.WriteLine("sum of product of all " +
                      "pairs of array elements : " +
                       findProductSum(A, n));
}
}
 
// This code is contributed by Akanksha Rai

<?php
// Efficient PHP program to find sum
// pair products in an array.
 
// required function
function findProductSum(&$A, $n)
{
    // calculating array sum (a1 + a2 ... + an)
    $array_sum = 0;
    for ($i = 0; $i < $n; $i++)
        $array_sum = $array_sum + $A[$i];
 
    // calculating square of array sum
    // (a1 + a2 + ... + an)^2
    $array_sum_square = $array_sum * $array_sum;
 
    // calculating a1^2 + a2^2 + ... + an^2
    $individual_square_sum = 0;
    for ($i = 0; $i < $n; $i++)
        $individual_square_sum += $A[$i] * $A[$i];
 
    // required sum is (array_sum_square -
    // individual_square_sum) / 2
    return ($array_sum_square -
            $individual_square_sum) / 2;
}
 
// Driver code
$A = array(1, 3, 4);
$n = sizeof($A);
echo("sum of product of all pairs " .
             "of array elements : ");
echo (findProductSum($A, $n));
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
    // Efficient Javascript program to find sum pair
    // products in an array.
     
    // required function
    function findProductSum(A, n)
    {
        // calculating array sum (a1 + a2 ... + an)
        let array_sum = 0;
        for (let i = 0; i < n; i++)
            array_sum = array_sum + A[i];
 
        // calculating square of array sum
        // (a1 + a2 + ... + an)^2
        let array_sum_square = array_sum * array_sum;
 
        // calculating a1^2 + a2^2 + ... + an^2
        let individual_square_sum = 0;
        for (let i = 0; i < n; i++)
            individual_square_sum += A[i] * A[i];
 
        // required sum is (array_sum_square -
        // individual_square_sum) / 2
        return (array_sum_square - individual_square_sum) / 2;
    }
     
    let A = [1, 3, 4];
    let n = A.length;
    document.write("sum of product of all " +
                      "pairs of array elements : " +
                       findProductSum(A, n));
     
    // This code is contributed by rameshtravel07.
</script>

Producción: 

sum of product of all pairs of array elements : 19

Complejidad de tiempo: O(n) 
Complejidad de espacio: O(1)

Otra solución eficiente:

Para números grandes cuando también deberíamos trabajar con módulo de 10^9+7. El enfoque anterior puede no funcionar. Entonces, la intuición para este enfoque es para cada número si lo multiplicamos con el prefijo suma, entonces se cubren todos los pares antes del elemento y luego el elemento se agrega a la suma, lo que nos garantizará la multiplicación de pares después del elemento.

Ejemplos:

Input : A[] = {1, 3, 4, 5}
Output : 59
Possible Pairs : (1,3), (1,4), (1,5), (3,4), (3,5), (4,5)
Sum of Product : 1*3 + 1*4 + 1*5 + 3*4 + 3*5 +4*5 = 59
Intuition:
Initially ans=0, sum=0, i=0.so,
i=k :
    ans+=sum*A[k];
    sum+=A[k];
--------------------------------------
i=0 :A[i]=1
    ans+=(0)*(1);    ans==0
    sum+=1;            sum==1 (1)
i=1 : A[i]=3
    ans+=(1)*(3);    ans==3
    sum+=3;            sum==4 (1+3)
i=2 : A[i]=4
    ans+=(4)*(4);    ans==19
    sum+=4;            sum==8 (1+3+4)
i=3 : A[i]=5
    ans+=(8)*(5);    ans==59
    sum+=5;            sum==13 (1+3+4+5)
    
So, ans=59.

// Efficient C++ program to find sum pair products
// in an array.
#include <iostream>
using namespace std;
 
// required function
int findProductSum(int A[], int N)
{
    long long ans = 0;
    long long sum = 0;
    long long Mod = 1000000007;
    for (int i = 0; i < N; i++) {
        ans += (sum * A[i]) % Mod;
        ans %= Mod;
        sum += A[i];
        sum %= Mod;
    }
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 1, 3, 4 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Sum of product of all pairs of array elements : "
         << findProductSum(A, n);
    return 0;
}
 
// This code is contributed by Kasina Dheeraj.

Producción:

Sum of product of all pairs of array elements : 19

Tiempo Complejidad : O(n)  
Espacio Auxiliar : O(1)

Este artículo es una contribución de Pratik Chhajer . 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.