Given an array A[] of integers find sum of product of all pairs of array elements i. e., we need to find of product after execution of following pseudo code
product = 0
for i = 1:n
for j = i+1:n
product = product + A[i]*A[j]
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
For each index i we loop through j=i+1 to j=n and add A[i]*A[j] each time. Below is implementation for the same.
C++
#include <iostream>
using namespace std;
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;
}
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;
}
|
Java
import java.io.*;
class test
{
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 {
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));
}
}
|
Python3
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
if __name__ = = "__main__" :
A = [ 1 , 3 , 4 ]
n = len (A)
print ( "sum of product of all pairs "
"of array elements : " ,findProductSum(A, n))
|
C#
using System;
class GFG
{
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;
}
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));
}
}
|
PHP
<?php
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 ;
}
$A = array (1, 3, 4);
$n = sizeof( $A );
echo "sum of product of all pairs " ,
"of array elements : "
,findProductSum( $A , $n );
?>
|
Javascript
<script>
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;
}
let A = [1, 3, 4];
let n = A.length;
document.write( "sum of product of all pairs " +
"of array elements : " + findProductSum(A, n));
</script>
|
sum of product of all pairs of array elements : 19
Time Complexity : O(n2)
Space Complexity : O(1)
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
C++
#include <iostream>
using namespace std;
int findProductSum( int A[], int n)
{
int array_sum = 0;
for ( int i = 0; i < n; i++)
array_sum = array_sum + A[i];
int array_sum_square = array_sum * array_sum;
int individual_square_sum = 0;
for ( int i = 0; i < n; i++)
individual_square_sum += A[i]*A[i];
return (array_sum_square - individual_square_sum)/2;
}
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;
}
|
Java
class GFG
{
static int findProductSum( int A[], int n)
{
int array_sum = 0 ;
for ( int i = 0 ; i < n; i++)
array_sum = array_sum + A[i];
int array_sum_square = array_sum * array_sum;
int individual_square_sum = 0 ;
for ( int i = 0 ; i < n; i++)
individual_square_sum += A[i] * A[i];
return (array_sum_square - individual_square_sum) / 2 ;
}
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));
}
}
|
Python3
def findProductSum(A, n):
array_sum = 0
for i in range ( 0 , n, 1 ):
array_sum = array_sum + A[i]
array_sum_square = array_sum * array_sum
individual_square_sum = 0
for i in range ( 0 , n, 1 ):
individual_square_sum + = A[i] * A[i]
return (array_sum_square -
individual_square_sum) / 2
if __name__ = = '__main__' :
A = [ 1 , 3 , 4 ]
n = len (A)
print ( "sum of product of all pairs of" ,
"array elements :" , int (findProductSum(A, n)))
|
C#
using System;
class GFG
{
static int findProductSum( int [] A, int n)
{
int array_sum = 0;
for ( int i = 0; i < n; i++)
array_sum = array_sum + A[i];
int array_sum_square = array_sum * array_sum;
int individual_square_sum = 0;
for ( int i = 0; i < n; i++)
individual_square_sum += A[i] * A[i];
return (array_sum_square -
individual_square_sum) / 2;
}
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));
}
}
|
PHP
<?php
function findProductSum(& $A , $n )
{
$array_sum = 0;
for ( $i = 0; $i < $n ; $i ++)
$array_sum = $array_sum + $A [ $i ];
$array_sum_square = $array_sum * $array_sum ;
$individual_square_sum = 0;
for ( $i = 0; $i < $n ; $i ++)
$individual_square_sum += $A [ $i ] * $A [ $i ];
return ( $array_sum_square -
$individual_square_sum ) / 2;
}
$A = array (1, 3, 4);
$n = sizeof( $A );
echo ( "sum of product of all pairs " .
"of array elements : " );
echo (findProductSum( $A , $n ));
?>
|
Javascript
<script>
function findProductSum(A, n)
{
let array_sum = 0;
for (let i = 0; i < n; i++)
array_sum = array_sum + A[i];
let array_sum_square = array_sum * array_sum;
let individual_square_sum = 0;
for (let i = 0; i < n; i++)
individual_square_sum += A[i] * A[i];
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));
</script>
|
sum of product of all pairs of array elements : 19
Time Complexity : O(n)
Space Complexity : O(1)
Another Efficient Solution:
For large numbers when we should also work with modulus of 10^9+7. The above approach may not work. So the Intuition for this approach is for each number if we multiply it with prefix sum then all pair before the element are covered and then element is added to the sum which will guarantee us with the multiplication of pairs after the element.
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.
C++
#include <iostream>
using namespace std;
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;
}
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;
}
|
Java
import java.io.*;
class GFG {
static int findProductSum( int [] A, int N)
{
long ans = 0 ;
long sum = 0 ;
long Mod = 1000000007 ;
for ( int i = 0 ; i < N; i++) {
ans += (sum * A[i]) % Mod;
ans %= Mod;
sum += A[i];
sum %= Mod;
}
return ( int )ans;
}
public static void main(String[] args)
{
int [] A = { 1 , 3 , 4 };
int n = A.length;
System.out.print(
"Sum of product of all pairs of array elements : "
+ findProductSum(A, n));
}
}
|
Python3
def findProductSum(A, N):
ans = 0
Sum = 0
Mod = 1000000007
for i in range (N):
ans + = ( Sum * A[i]) % Mod
ans % = Mod
Sum + = A[i]
Sum % = Mod
return ans
A = [ 1 , 3 , 4 ]
n = len (A)
print ( "Sum of product of all pairs of array elements :" , findProductSum(A, n))
|
C#
using System;
public class GFG
{
static int findProductSum( int [] A, int N)
{
long ans = 0;
long sum = 0;
long Mod = 1000000007;
for ( int i = 0; i < N; i++) {
ans += (sum * A[i]) % Mod;
ans %= Mod;
sum += A[i];
sum %= Mod;
}
return ( int )ans;
}
static public void Main()
{
int [] A = { 1, 3, 4 };
int n = A.Length;
Console.Write(
"Sum of product of all pairs of array elements : "
+ findProductSum(A, n));
}
}
|
Javascript
class GFG
{
static findProductSum(A, N)
{
var ans = 0;
var sum = 0;
var Mod = 1000000007;
for ( var i=0; i < N; i++)
{
ans += (sum * A[i]) % Mod;
ans %= Mod;
sum += A[i];
sum %= Mod;
}
return parseInt(ans);
}
static main(args)
{
var A = [1, 3, 4];
var n = A.length;
console.log( "Sum of product of all pairs of array elements : " + GFG.findProductSum(A, n));
}
}
GFG.main([]);
|
Sum of product of all pairs of array elements : 19
Time Complexity : O(n)
Auxiliary Space : O(1)
Contact Us