Data Modelling & AI Data Structure & Algorithm

Sum of products of all possible Subarrays

23 June 2025

0

Given an array arr[] of N positive integers, the task is to find the sum of the product of elements of all the possible subarrays.

Examples:

Input: arr[] = {1, 2, 3}
Output: 20
Explanation: Possible Subarrays are: {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}.
Products of all the above subarrays are 1, 2, 3, 2, 6 and 6 respectively.
Sum of all products = 1 + 2 + 3 + 2 + 6 + 6 = 20.

Input: arr[] = {1, 2, 3, 4}
Output: 84
Explanation:
Possible Subarrays are: {1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}. Products of all the above subarrays are 1, 2, 3, 4, 2, 6, 12, 6, 24 and 24.
Sum of all products = 1 + 2 + 3 + 4 + 2 + 6 + 12 + 6 + 24 + 24 = 84.

Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays and calculate the product of all elements of each subarray and add it to the final sum.

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to observe the problem into some pattern. Suppose we have four numbers a, b, c, and d. We can write all possible subarrays products as:

a + b + c + d+ ab + bc + cd + abc + bcd + abcd
= (a + ab + abc + abcd) + (b + bc + bcd) + (c + cd) + d
= a * (1+ b + bc + bcd) + (b + bc + bcd) + (c + cd) + d

Now, the value of underlined expression (b + bc + bcd) can be calculated once and use twice.
Again, (b+ bc + bcd) + (c + cd) = b * (1 + c + cd) + (c + cd)

In the same way, the expression (c + cd) can be used twice.
The latter part is the same as above.

Follow the below steps to solve the problem:

Iterate through the last element and make the reoccurring expression updated with every element and use it further. In this process, update the result accordingly.
Initialize the ans as 0 that will store the final sum and res as 0 that will keep the track of the value of the product of all elements of the previous subarray.
Traverse the array from the back and for each element, arr[i] do the following:
- Increment the ans by the product of arr[i] and (1 + res).
- Update res to arr[i]*(1 + res).
After the above steps, print the sum of the product of all subarrays stored in ans.

Below is the implementation of the above approach:

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the sum of
// products of all subarray of arr[]
void sumOfSubarrayProd(int arr[], int n)
{
     
    // Stores sum of all subarrays
    int ans = 0;
    int res = 0;
 
    // Iterate array from behind
    for(int i = n - 1; i >= 0; i--) 
    {
        int incr = arr[i] * (1 + res);
 
        // Update the ans
        ans += incr;
 
        // Update the res
        res = incr;
    }
 
    // Print the final sum
    cout << (ans);
}
 
// Driver Code
int main()
{
     
    // Given array arr[]
    int arr[] = { 1, 2, 3 };
 
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    sumOfSubarrayProd(arr, N);
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
 
import java.io.*;
class GFG {
 
    // Function that finds the sum of
    // products of all subarray of arr[]
    static void sumOfSubarrayProd(int arr[],
                                  int n)
    {
        // Stores sum of all subarrays
        int ans = 0;
        int res = 0;
 
        // Iterate array from behind
        for (int i = n - 1; i >= 0; i--) {
            int incr = arr[i] * (1 + res);
 
            // Update the ans
            ans += incr;
 
            // Update the res
            res = incr;
        }
 
        // Print the final sum
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 1, 2, 3 };
 
        // Size of array
        int N = arr.length;
 
        // Function Call
        sumOfSubarrayProd(arr, N);
    }
}

Python3

# Python3 program for the above approach
 
# Function that finds the sum of
# products of all subarray of arr[]
def sumOfSubarrayProd(arr, n):
     
    # Stores sum of all subarrays
    ans = 0
    res = 0
 
    # Iterate array from behind
    i = n - 1
    while(i >= 0):
        incr = arr[i] * (1 + res)
 
        # Update the ans
        ans += incr
 
        # Update the res
        res = incr
        i -= 1
 
    # Print the final sum
    print(ans)
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 1, 2, 3 ]
 
    # Size of array
    N = len(arr)
 
    # Function call
    sumOfSubarrayProd(arr, N)
     
# This code is contributed by ipg2016107

C#

// C# program for the 
// above approach
using System;
 
// Function that finds 
// the sum of products 
// of all subarray of arr[]
class solution{
 
static void sumOfSubarrayProd(int []arr, 
                              int n)
{    
  // Stores sum of all 
  // subarrays
  int ans = 0;
  int res = 0;
 
  // Iterate array from behind
  for(int i = n - 1; i >= 0; i--) 
  {
    int incr = arr[i] * (1 + res);
 
    // Update the ans
    ans += incr;
 
    // Update the res
    res = incr;
  }
 
  // Print the final sum
  Console.WriteLine(ans);
}
 
// Driver Code
public static void Main(String[] args)
{    
  // Given array arr[]
  int []arr = {1, 2, 3 };
 
  // Size of array
  int N = arr.Length;
  // Function call
  sumOfSubarrayProd(arr, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
// Javascript program to implement
// the above approach
 
// Function that finds the sum of
    // products of all subarray of arr[]
    function sumOfSubarrayProd(arr, n)
    {
        // Stores sum of all subarrays
        let ans = 0;
        let res = 0;
  
        // Iterate array from behind
        for (let i = n - 1; i >= 0; i--) {
            let incr = arr[i] * (1 + res);
  
            // Update the ans
            ans += incr;
  
            // Update the res
            res = incr;
        }
  
        // Print the final sum
        document.write(ans);
    }
 
    // Driver Code
     
     // Given array arr[]
        let arr = [ 1, 2, 3 ];
  
        // Size of array
        let N = arr.length;
  
        // Function Call
        sumOfSubarrayProd(arr, N);
      
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Sum of products of all possible Subarrays

C++14

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

Cyber Threat-Sharing Law Nears Expiration: Experts Warn of Risks by Husain Parvez

The Galaxy S7 is everything I used to love about Samsung

Bose’s TV Speaker drops to its best price yet for Labor Day

EDITOR PICKS

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

Cyber Threat-Sharing Law Nears Expiration: Experts Warn of Risks by Husain Parvez

The Galaxy S7 is everything I used to love about Samsung

POPULAR POSTS

Over 30,000 Malicious IPs Target Microsoft Remote Desktop in Global Surge by Husain Parvez

Cyber Threat-Sharing Law Nears Expiration: Experts Warn of Risks by Husain Parvez

The Galaxy S7 is everything I used to love about Samsung

POPULAR CATEGORY

ABOUT US

FOLLOW US