Given an array arr[] of n integers. The task is to find the sum of product of each element with each element after it in the array. In other words, find sum of product of each arr[i] with each arr[j] such that j > i.
Examples :
Input : arr[] = {9, 3, 4, 2}
Output : 107
Explanation:
Sum of product of arr[0] with arr[1], arr[2], arr[3] is 9*3 + 9*4 + 9*2 = 81
Sum of product of arr[1] with arr[2], arr[3] is 3*4 + 3*2 = 18
Product of arr[2] with arr[3] is 4*2 = 8
Sum of all these sums is 81 + 18 + 8 = 107Input : arr[] = {3, 5}
Output : 15
Observe to find (p*a + p*b + …..+ p*y + p*z) is equals to p*(a + b ….. y + z).
So for each i, 0 ? i ? n – 2 we have to calculate arr[i] * (arr[j] + arr[j+1] + ….. + arr[n – 2] + arr[n – 1]), where j = i + 1 and find sum of these.
We can reduce the complexity of finding (arr[j] + arr[j+1] + ….. + arr[n – 2] + arr[n – 1]) for each ‘i’ by precomputing the suffix sum of the array.
Lets sum[] stores the suffix sum of the given array i.e sum[i] have arr[i] + arr[i+1] + ….. + arr[n – 2] + arr[n – 1].
So, after precompute sum[], we need to find the sum of arr[i]*sum[i + 1] where 0 ? i ? n – 2.
Below is the implementation of this approach:
C++
// C++ Program to find sum of // product of each element// with each element after it#include <bits/stdc++.h>using namespace std;// Return sum of product // of each element with // each element after itint findSumofProduct(int arr[], int n){ int sum[n]; sum[n - 1] = arr[n - 1]; // finding suffix sum for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + arr[i]; // finding the sum of product of // each element with suffix sum. int res = 0; for (int i = 0; i < n - 1; i++) res += (sum[i + 1] * arr[i]); return res;}// Driver Codeint main(){ int arr[] = {9, 3, 4, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << findSumofProduct(arr, n) << endl; return 0;} |
Java
// Java Program to find sum of product// of each element with each element// after itclass GFG { // Return sum of product of each // element with each element // after it static int findSumofProduct(int arr[], int n) { int sum[] = new int[n]; sum[n - 1] = arr[n - 1]; // finding suffix sum for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + arr[i]; // finding the sum of product of // each element with suffix sum. int res = 0; for (int i = 0; i < n - 1; i++) res += (sum[i + 1] * arr[i]); return res; } // Driver Program public static void main(String[] args) { int arr[] = { 9, 3, 4, 2 }; int n = arr.length; System.out.println( findSumofProduct(arr, n)); }}// This code is contributed by// Smitha Dinesh Semwal |
Python3
# Python3 Program to find sum of # product of each element with # each element after it # Return sum of product of each # element with each element after it def findSumofProduct(arr, n): sum = [None for _ in range(n)] sum[n-1] = arr[n - 1] # finding suffix sum for i in range(n - 2, -1, -1): sum[i] = sum[i + 1] + arr[i] # finding the sum of product of # each element with suffix sum. res = 0 for i in range(n - 1): res += sum[i + 1] * arr[i] return res# Driver Codearr = [9, 3, 4, 2]n = len(arr)print(findSumofProduct(arr, n))# This code is contributed# by SamyuktaSHegde |
C#
// C# Program to find sum of product// of each element with each element// after itusing System;class GFG { // Return sum of product of each // element with each element // after it static int findSumofProduct(int[] arr, int n) { int[] sum = new int[n]; sum[n - 1] = arr[n - 1]; // finding suffix sum for (int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + arr[i]; // finding the sum of product of // each element with suffix sum. int res = 0; for (int i = 0; i < n - 1; i++) res += (sum[i + 1] * arr[i]); return res; } // Driver code static public void Main () { int[] arr = { 9, 3, 4, 2 }; int n = arr.Length; Console.WriteLine(findSumofProduct(arr, n)); }}// This code is contributed by Ajit. |
PHP
<?php// PHP Program to find sum of // product of each element// with each element after it// Return sum of product // of each element with // each element after itfunction findSumofProduct($arr, $n){ $sum = array(); $sum[$n - 1] = $arr[$n - 1]; // finding suffix sum for ( $i = $n - 2; $i >= 0; $i--) $sum[$i] = $sum[$i + 1] + $arr[$i]; // finding the sum of product of // each element with suffix sum. $res = 0; for ( $i = 0; $i < $n - 1; $i++) $res += ($sum[$i + 1] * $arr[$i]); return $res;} // Driver Code $arr = array(9, 3, 4, 2); $n = count($arr); echo findSumofProduct($arr, $n); // This code is contributed by anuJ_67.?> |
Javascript
<script>// Javascript Program to find sum of// product of each element// with each element after it// Return sum of product// of each element with// each element after itfunction findSumofProduct(arr, n){ let sum = new Array(n); sum[n - 1] = arr[n - 1]; // finding suffix sum for (let i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + arr[i]; // finding the sum of product of // each element with suffix sum. let res = 0; for (let i = 0; i < n - 1; i++) res += (sum[i + 1] * arr[i]); return res;}// Driver Code let arr = [9, 3, 4, 2]; let n = arr.length; document.write(findSumofProduct(arr, n) + "<br>");// This code is contributed by Mayank Tyagi</script> |
Output
107
Time complexity: O(n) where n is the size of the given array
Auxiliary space: O(n)
Below is Optimized Code of finding sum of product of each element with each element after it:
C++
// C++ Program to find sum of// product of each element // with each element after it#include <bits/stdc++.h>using namespace std;// Return sum of product // of each element with // each element after itint findSumofProduct(int arr[], int n){ int suffix_sum = arr[n - 1]; // Finding product of array // elements and suffix sum. int res = 0; for (int i = n - 2; i >= 0; i--) { res += (suffix_sum * arr[i]); // finding suffix sum suffix_sum += arr[i]; } return res;}// Driver Codeint main(){ int arr[] = {9, 3, 4, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << findSumofProduct(arr, n) << endl; return 0;} |
Java
// Java Program to find sum // of product of each // element with each// element after itimport java .io.*;class GFG { // Return sum of product of // each element with each // element after it static int findSumofProduct(int[] arr, int n) { int suffix_sum = arr[n - 1]; // Finding product of array // elements and suffix sum. int res = 0; for (int i = n - 2; i >= 0; i--) { res += (suffix_sum * arr[i]); // finding suffix sum suffix_sum += arr[i]; } return res; } // Driver code static public void main(String[] args) { int[] arr = {9, 3, 4, 2}; int n = arr.length; System.out.println(findSumofProduct(arr, n)); }}// This code is contributed by anuj_67. |
Python 3
# Python 3 Program to find sum of# product of each element # with each element after it# Return sum of product # of each element with # each element after itdef findSumofProduct(arr, n): suffix_sum = arr[n - 1] # Finding product of array # elements and suffix sum. res = 0 for i in range(n - 2, -1, -1): res += (suffix_sum * arr[i]) # finding suffix sum suffix_sum += arr[i] return res;# Driver Codearr = [9, 3, 4, 2];n = len(arr);print(findSumofProduct(arr, n))# This code is contributed # by Akanksha Rai |
C#
// C# Program to find sum // of product of each // element with each// element after itusing System;class GFG { // Return sum of product of // each element with each // element after it static int findSumofProduct(int[] arr, int n) { int suffix_sum = arr[n - 1]; // Finding product of array // elements and suffix sum. int res = 0; for (int i = n - 2; i >= 0; i--) { res += (suffix_sum * arr[i]); // finding suffix sum suffix_sum += arr[i]; } return res; } // Driver code static public void Main() { int[] arr = {9, 3, 4, 2}; int n = arr.Length; Console.WriteLine(findSumofProduct(arr, n)); }}// This code is contributed by Ajit. |
PHP
<?php// PHP Program to find sum of// product of each element // with each element after it// Return sum of product // of each element with // each element after itfunction findSumofProduct($arr, $n){ $suffix_sum = $arr[$n - 1]; // Finding product of array // elements and suffix sum. $res = 0; for ( $i = $n - 2; $i >= 0; $i--) { $res += ($suffix_sum * $arr[$i]); // finding suffix sum $suffix_sum += $arr[$i]; } return $res;} // Driver Code $arr = array(9, 3, 4, 2); $n = count($arr); echo findSumofProduct($arr, $n) // This code is contributed by anuJ_67.?> |
Javascript
<script> // Javascript Program to find sum // of product of each // element with each // element after it // Return sum of product of // each element with each // element after it function findSumofProduct(arr, n) { let suffix_sum = arr[n - 1]; // Finding product of array // elements and suffix sum. let res = 0; for (let i = n - 2; i >= 0; i--) { res += (suffix_sum * arr[i]); // finding suffix sum suffix_sum += arr[i]; } return res; } let arr = [9, 3, 4, 2]; let n = arr.length; document.write(findSumofProduct(arr, n)); </script> |
Output
107
Time complexity: O(n) where n is the size of the given array
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
