Given an array arr[] of size N, the task is to find the sum of all products of ordered pairs that can be generated from the given array elements.
Examples:
Input: arr[] ={1, 2, 3}
Output: 36
Explanation:All possible pairs are {(1, 1), {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}. Therefore, the sum of product of all pairs is 36.Input : arr[]={3, 4, 1, 2, 5}
Output: 225Â
Naive Approach: The simplest approach is to iterate through all possible pairs from the given array calculate the sum of product of all pair-products.Â
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
arr[]={a1, a2, a3, a4 ….., an-1, an}
Now, sum of product of all  possible pairs is =
{
(a1 * a1) + (a1 * a2) + (a1 * a3) + …..+ (a1 * an-1) + (a1, an) +
(a2 * a1) + (a2 * a2) + (a2 * a3) + ….. + (a2 * an-1) + (a2 * an) +
(a3 * a1) + (a3 * a2) + (a3 * a3) + ….. + (a3 * an-1) + (a3, an) +
…………………………………………………………………………..
(an, * a1) + (an * a2), +(an * a3) + ….. + (an * an-1) + (an, an)
}={
(a1 + a2+  a3 + …..+ an-1 +  an ) * (a1 + a2+  a3 + …..+ an-1 +  an )Â
}
=(a1 + a2+  a3 + …..+ an-1 +  an )2
Follow the steps below to solve the problem:Â
- Initialize the variable, res=0 to store the sum of array elements
- Traverse the array, arr[] and add each element of the array to res.
- Finally, print the square of the res as the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach Â
#include <bits/stdc++.h> using namespace std; Â
// Function to calculate the // sum of all pair-products int sumOfProd(int arr[], int N) {     // Stores sum of array     int sum = 0; Â
    for (int i = 0; i < N; i++) { Â
        // Update sum of the array         sum += arr[i];     } Â
    return sum * sum; } Â
// Driver Code int main() { Â Â Â Â int arr[] = { 2, 3, 1, 5, 4 }; Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]); Â Â Â Â cout << sumOfProd(arr, N); Â Â Â Â return 0; } |
Java
// Java program to implement // the above approach import java.util.*; Â
class GFG{ Â
// Function to calculate the // sum of all pair-products static int sumOfProd(int arr[], int N) {          // Stores sum of array     int sum = 0; Â
    for(int i = 0; i < N; i++)     {                  // Update sum of the array         sum += arr[i];     }     return sum * sum; } Â
// Driver code public static void main(String[] args) { Â Â Â Â int arr[] = { 2, 3, 1, 5, 4 }; Â Â Â Â int N = arr.length; Â Â Â Â Â Â Â Â Â System.out.print(sumOfProd(arr, N)); } } Â
// This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach Â
# Function to calculate the # sum of all pair-products def sumOfProd(arr, N):         # Stores sum of array     sum = 0Â
    for i in range(N):                 # Update sum of the array         sum += arr[i]Â
    return sum * sumÂ
# Driver Code if __name__ == '__main__':Â Â Â Â Â Â Â Â Â arr = [ 2, 3, 1, 5, 4 ] Â Â Â Â N = len(arr) Â Â Â Â Â Â Â Â Â print(sumOfProd(arr, N))Â
# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement // the above approach  using System;Â
class GFG{     // Function to calculate the // sum of all pair-products static int sumOfProd(int[] arr, int N) {          // Stores sum of array     int sum = 0;        for(int i = 0; i < N; i++)    {                 // Update sum of the array         sum += arr[i];     }     return sum * sum; }  Â
// Driver codestatic void Main() {Â Â Â Â int[] arr = { 2, 3, 1, 5, 4 };Â Â Â Â Â int N = arr.Length;Â Â Â Â Â Â Â Â Â Â Console.WriteLine(sumOfProd(arr, N));}}Â
// This code is contributed by divyeshrabadiya07 |
Javascript
<script>Â
// JavaScript program for the above approachÂ
// Function to calculate the// sum of all pair-productsfunction sumOfProd(arr, N){          // Stores sum of array    let sum = 0;      for(let i = 0; i < N; i++)    {                  // Update sum of the array        sum += arr[i];    }    return sum * sum;}  // Driver CodeÂ
       let arr = [ 2, 3, 1, 5, 4 ];    let N = arr.length;          document.write(sumOfProd(arr, N));Â
// This code is contributed by souravghosh0416.</script> |
Output:
225
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
