Given an array arr[] and two integers L and R. The task is to find the sum of the product of all the pairs (i, j) in the range [L, R], such that i ≤ j.
Input: arr[] = { 1, 3, 5, 8 }, L = 0, R = 2
Output: 58
Explanation: As 1*1 + 1*3 + 1*5 + 3*3 + 3*5 + 5*5 = 58Input: arr[] = { 2, 1, 4, 5, 3, 2, 1 }, L = 1, R = 5
Output: 140
Naive Approach: The brute force approach can be directly implemented by multiplying the indices using two nested loops and storing the sum in a variable.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return the sum// of (arr[i]*arr[j]) for all i and j// between the index L and Rint sum_of_products(int arr[], int N, int L, int R){ int sum = 0; for (int i = L; i <= R; i++) { for (int j = i; j <= R; j++) { sum += arr[i] * arr[j]; } } return sum;}// Driver codeint main(){ int arr[] = { 1, 3, 5, 8 }; int N = sizeof(arr) / sizeof(arr[0]); int L = 0; int R = 2; cout << sum_of_products(arr, N, L, R); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;public class GFG { // Function to return the sum // of (arr[i]*arr[j]) for all i and j // between the index L and R static int sum_of_products(int[] arr, int N, int L, int R) { int sum = 0; for (int i = L; i <= R; i++) { for (int j = i; j <= R; j++) { sum += arr[i] * arr[j]; } } return sum; } // Driver code public static void main(String args[]) { int[] arr = { 1, 3, 5, 8 }; int N = arr.length; int L = 0; int R = 2; System.out.println(sum_of_products(arr, N, L, R)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach:## Function to return the sum## of (arr[i]*arr[j]) for all i and j## between the index L and Rdef sum_of_products(arr, N, L, R): sum1 = 0 for i in range(L, R + 1): for j in range(i, R + 1): sum1 += arr[i] * arr[j] return sum1## Driver codeif __name__ == "__main__": arr = [ 1, 3, 5, 8 ] N = len(arr) L = 0 R = 2 print(sum_of_products(arr, N, L, R)) # This code is contributed by entertain2022. |
C#
// C# implementation of the above approachusing System;class GFG { // Function to return the sum // of (arr[i]*arr[j]) for all i and j // between the index L and R static int sum_of_products(int[] arr, int N, int L, int R) { int sum = 0; for (int i = L; i <= R; i++) { for (int j = i; j <= R; j++) { sum += arr[i] * arr[j]; } } return sum; } // Driver code public static void Main() { int[] arr = { 1, 3, 5, 8 }; int N = arr.Length; int L = 0; int R = 2; Console.WriteLine(sum_of_products(arr, N, L, R)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to return the sum // of (arr[i]*arr[j]) for all i and j // between the index L and R function sum_of_products(arr, N, L, R) { let sum = 0; for (let i = L; i <= R; i++) { for (let j = i; j <= R; j++) { sum += arr[i] * arr[j]; } } return sum; } // Driver code let arr = [1, 3, 5, 8]; let N = arr.length let L = 0; let R = 2; document.write(sum_of_products(arr, N, L, R)); // This code is contributed by Potta Lokesh </script> |
Output
58
Time complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: This problem can be efficiently solved by using the Prefix sum technique. In this method, store the prefix sum in pre-calculation and then iterate a single loop from L to R and multiply the corresponding prefix sum from that index to the last index.
Basically 1*1+1*3+1*5+3*3+3*5+5*5 can be written as 1*(1+3+5)+3*(3+5)+5*(5) = 1*(prefix_sum from 1 to 5)+3*(prefix_sum from 3 to 5)+5*(prefix sum from 5 to 5)
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to return the sum of// (arr[i]*arr[j]) for all i and j// between the index L and Rint sum_of_products(int arr[], int n, int L, int R){ int sum = 0; // Pre-calculating Prefix sum int prefix_sum[n]; prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i]; } // Using prefix sum to find // summation of products for (int i = L; i <= R; i++) { // if-else for i==0 case // in prefix sum if (i != 0) sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]); else sum += arr[i] * (prefix_sum[R]); } return sum;}// Driver codeint main(){ int arr[] = { 1, 3, 5, 8 }; int N = sizeof(arr) / sizeof(arr[0]); int L = 0; int R = 2; cout << sum_of_products(arr, N, L, R); return 0;} |
Java
// Java code to implement above approachimport java.util.*;class GFG{ // Function to return the sum of // (arr[i]*arr[j]) for all i and j // between the index L and R static int sum_of_products(int arr[], int n, int L, int R) { int sum = 0; // Pre-calculating Prefix sum int []prefix_sum = new int[n]; prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i]; } // Using prefix sum to find // summation of products for (int i = L; i <= R; i++) { // if-else for i==0 case // in prefix sum if (i != 0) sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]); else sum += arr[i] * (prefix_sum[R]); } return sum; } // Driver code public static void main(String[] args) { int arr[] = { 1, 3, 5, 8 }; int N = arr.length; int L = 0; int R = 2; System.out.print(sum_of_products(arr, N, L, R)); }}// This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach:## Function to return the sum of## (arr[i]*arr[j]) for all i and j## between the index L and Rdef sum_of_products(arr, n, L, R): sum = 0 ## Pre-calculating Prefix sum prefix_sum = [0]*n; prefix_sum[0] = arr[0]; for i in range(1, n): prefix_sum[i] = prefix_sum[i - 1] + arr[i] ## Using prefix sum to find ## summation of products for i in range(L, R + 1): ## if-else for i==0 case ## in prefix sum if (i != 0): sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]) else: sum += arr[i] * (prefix_sum[R]) return sum## Driver codeif __name__=='__main__': arr = [1, 3, 5, 8] N = len(arr) L = 0 R = 2 print(sum_of_products(arr, N, L, R)) # This code is contributed by subhamgoyal2014. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to return the sum of // (arr[i]*arr[j]) for all i and j // between the index L and R static int sum_of_products(int[] arr, int n, int L, int R) { int sum = 0; // Pre-calculating Prefix sum int []prefix_sum = new int[n]; prefix_sum[0] = arr[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i]; } // Using prefix sum to find // summation of products for (int i = L; i <= R; i++) { // if-else for i==0 case // in prefix sum if (i != 0) sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]); else sum += arr[i] * (prefix_sum[R]); } return sum; } // Driver Code public static void Main() { int[] arr = { 1, 3, 5, 8 }; int N = arr.Length; int L = 0; int R = 2; Console.Write(sum_of_products(arr, N, L, R)); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript code to implement above approach // Function to return the sum of // (arr[i]*arr[j]) for all i and j // between the index L and R function sum_of_products(arr , n , L , R) { var sum = 0; // Pre-calculating Prefix sum var prefix_sum = Array(n).fill(0); prefix_sum[0] = arr[0]; for (i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i]; } // Using prefix sum to find // summation of products for (i = L; i <= R; i++) { // if-else for i==0 case // in prefix sum if (i != 0) sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]); else sum += arr[i] * (prefix_sum[R]); } return sum; } // Driver code var arr = [ 1, 3, 5, 8 ]; var N = arr.length; var L = 0; var R = 2; document.write(sum_of_products(arr, N, L, R));// This code is contributed by umadevi9616</script> |
Output
58
Time complexity: O(N)
Auxiliary Space: O(N)
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!
