Naive Solution
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++
// 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; } |
Java
/*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)); } } |
Python3
# 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)) |
C#
// 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
<?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 ?> |
Javascript
<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> |
Output:
sum of product of all pairs of array elements : 19
Time Complexity : O(n2)
Space Complexity : O(1)
Sum of product of all pairs of array elements
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]
Examples:
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