Given an integer array ‘arr[]’ of size N, find the sum of all sub-arrays of the given array.
Examples:
Input: arr[] = {1, 2, 3}
Output: 20
Explanation: {1} + {2} + {3} + {2 + 3} + {1 + 2} + {1 + 2 + 3} = 20Input: arr[] = {1, 2, 3, 4}
Output: 50
Naive Approach: To solve the problem follow the below idea:
A simple solution is to generate all sub-arrays and compute their sum
Follow the below steps to solve the problem:
- Generate all subarrays using nested loops
- Take the sum of all these subarrays
Below is the implementation of the above approach:
C++
// Simple C++ program to compute sum of// subarray elements#include <bits/stdc++.h>using namespace std;// Computes sum all sub-arraylong int SubArraySum(int arr[], int n){ long int result = 0, temp = 0; // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point temp = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points temp += arr[j]; result += temp; } } return result;}// Driver codeint main(){ int arr[] = { 1, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Sum of SubArray : " << SubArraySum(arr, n) << endl; return 0;} |
Java
// Java program to compute sum of// subarray elementsclass GFG { // Computes sum all sub-array public static long SubArraySum(int arr[], int n) { long result = 0, temp = 0; // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point temp = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points temp += arr[j]; result += temp; } } return result; } /* Driver code */ public static void main(String[] args) { int arr[] = { 1, 2, 3 }; int n = arr.length; System.out.println("Sum of SubArray : " + SubArraySum(arr, n)); }}// This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to compute# sum of subarray elements# Computes sum all sub-arraydef SubArraySum(arr, n): temp, result = 0, 0 # Pick starting point for i in range(0, n): # Pick ending point temp = 0 for j in range(i, n): # sum subarray between # current starting and # ending points temp += arr[j] result += temp return result# Driver codearr = [1, 2, 3]n = len(arr)print("Sum of SubArray :", SubArraySum(arr, n))# This code is contributed by# TheGameOf256. |
C#
// C# program to compute sum of// subarray elementsusing System;class GFG { // Computes sum all sub-array public static long SubArraySum(int[] arr, int n) { long result = 0, temp = 0; // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point temp = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points temp += arr[j]; result += temp; } } return result; } // Driver Code public static void Main() { int[] arr = { 1, 2, 3 }; int n = arr.Length; Console.Write("Sum of SubArray : " + SubArraySum(arr, n)); }}// This code is contributed by nitin mittal |
PHP
<?php// Simple PHP program to // compute sum of subarray // elements Computes sum// all sub-arrayfunction SubArraySum($arr, $n){ $result = 0; $temp = 0; // Pick starting point for ($i = 0; $i < $n; $i++) { // Pick ending point $temp=0; for ($j = $i; $j < $n; $j++) { // sum subarray between // current starting and // ending points $temp+=$arr[$j]; $result += $temp ; } } return $result ;}// Driver Code$arr = array(1, 2, 3) ;$n = sizeof($arr);echo "Sum of SubArray : ", SubArraySum($arr, $n),"\n"; // This code is contributed by ajit?> |
Javascript
<script>// Simple Javascript program to compute sum of // subarray elements // Computes sum all sub-array function SubArraySum(arr, n) { let result = 0,temp=0; // Pick starting point for (let i=0; i <n; i++) { // Pick ending point temp=0; for (let j=i; j<n; j++) { // sum subarray between current // starting and ending points temp+=arr[j]; result += temp ; } } return result ; } // driver program to test above function let arr = [1, 2, 3] ; let n = arr.length; document.write("Sum of SubArray : " + SubArraySum(arr, n) + "<br>"); // This code is contributed by Mayank Tyagi</script> |
Output
Sum of SubArray : 20
Time Complexity: O(N2)
Auxiliary Space: O(1)
Sum of all Subarrays using prefix-sum:
To solve the problem follow the below idea:
We can construct a prefix-sum array and extract the subarray sum between starting and ending indices of every subarray.
Follow the below steps to solve the problem:
- Create a prefix sum array for the input array
- Generate the starting and ending indices for all the possible subarrays
- Extract their sum from the prefix sum array and add it in the answer
- Return answer
Below is the implementation of the above approach:
C++
// C++ program to compute sum of// subarray elements#include <bits/stdc++.h>using namespace std;typedef long long ll;// Construct prefix-sum arrayvoid buildPrefixSumArray(int arr[], int n, int prefixSumArray[]){ prefixSumArray[0] = arr[0]; // Adding present element with previous element for (int i = 1; i < n; i++) prefixSumArray[i] = prefixSumArray[i - 1] + arr[i];}// Computes sum all sub-arrayll SubArraySum(int arr[], int n){ ll result = 0, sum = 0; int prefixSumArr[n] = { 0 }; buildPrefixSumArray(arr, n, prefixSumArr); // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point sum = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points if (i != 0) { sum = prefixSumArr[j] - prefixSumArr[i - 1]; } else sum = prefixSumArr[j]; result += sum; } } return result;}/* Driver code */int main(){ int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); ll ans = SubArraySum(arr, n); cout << "Sum of SubArray : " << ans << endl; return 0;}// This code is contributed by Kdheeraj. |
Java
// Java program to compute sum of// subarray elementsclass GFG { // Construct prefix-sum array public static void buildPrefixSumArray(int arr[], int n, int prefixSumArray[]) { prefixSumArray[0] = arr[0]; // Adding present element with previous element for (int i = 1; i < n; i++) prefixSumArray[i] = prefixSumArray[i - 1] + arr[i]; } // Computes sum all sub-array public static long SubArraySum(int arr[], int n) { long result = 0, sum = 0; int[] prefixSumArr = new int[n]; buildPrefixSumArray(arr, n, prefixSumArr); // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point sum = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points if (i != 0) { sum = prefixSumArr[j] - prefixSumArr[i - 1]; } else sum = prefixSumArr[j]; result += sum; } } return result; } /* Driver code */ public static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; int n = arr.length; System.out.println("Sum of SubArray : " + SubArraySum(arr, n)); }} |
Python3
# Python 3 program to compute sum of# subarray elementsclass GFG: # Construct prefix-sum array @staticmethod def buildPrefixSumArray(arr, n, prefixSumArray): prefixSumArray[0] = arr[0] # Adding present element with previous element i = 1 while (i < n): prefixSumArray[i] = prefixSumArray[i - 1] + arr[i] i += 1 # Computes sum all sub-array @staticmethod def SubArraySum(arr, n): result = 0 sum = 0 prefixSumArr = [0] * (n) GFG.buildPrefixSumArray(arr, n, prefixSumArr) # Pick starting point i = 0 while (i < n): # Pick ending point sum = 0 j = i while (j < n): # sum subarray between current # starting and ending points if (i != 0): sum = prefixSumArr[j] - prefixSumArr[i - 1] else: sum = prefixSumArr[j] result += sum j += 1 i += 1 return result # Driver code @staticmethod def main(args): arr = [1, 2, 3, 4] n = len(arr) print("Sum of SubArray : " + str(GFG.SubArraySum(arr, n)))if __name__ == "__main__": GFG.main([]) |
C#
// Include namespace systemusing System;// C# program to compute sum of// subarray elementspublic class GFG { // Construct prefix-sum array public static void buildPrefixSumArray(int[] arr, int n, int[] prefixSumArray) { prefixSumArray[0] = arr[0]; // Adding present element with previous element for (int i = 1; i < n; i++) { prefixSumArray[i] = prefixSumArray[i - 1] + arr[i]; } } // Computes sum all sub-array public static long SubArraySum(int[] arr, int n) { var result = 0; var sum = 0; int[] prefixSumArr = new int[n]; GFG.buildPrefixSumArray(arr, n, prefixSumArr); // Pick starting point for (int i = 0; i < n; i++) { // Pick ending point sum = 0; for (int j = i; j < n; j++) { // sum subarray between current // starting and ending points if (i != 0) { sum = prefixSumArr[j] - prefixSumArr[i - 1]; } else { sum = prefixSumArr[j]; } result += sum; } } return result; } // Driver code public static void Main(String[] args) { int[] arr = { 1, 2, 3, 4 }; var n = arr.Length; Console.WriteLine( "Sum of SubArray : " + GFG.SubArraySum(arr, n).ToString()); }}// This code is contributed by aadityaburujwale. |
Javascript
// Simple Javascript program to compute sum of// subarray elements // Construct prefix-sum array function buildPrefixSumArray(arr, n, prefixSumArray){ prefixSumArray[0] = arr[0]; // Adding present element with previous element for (let i = 1; i < n; i++) prefixSumArray[i] = prefixSumArray[i - 1] + arr[i];}// Computes sum all sub-arrayfunction SubArraySum(arr, n){ let result = 0, sum = 0; let prefixSumArr = []; for (let i = 0; i < n; i++) { prefixSumArr.push(0); } buildPrefixSumArray(arr, n, prefixSumArr); // Pick starting point for (let i = 0; i < n; i++) { // Pick ending point sum = 0; for (let j = i; j < n; j++) { // sum subarray between current // starting and ending points if (i != 0) { sum = prefixSumArr[j] - prefixSumArr[i - 1]; } else sum = prefixSumArr[j]; result += sum; } } return result;}/* Driver program to test above function */let arr = [ 1, 2, 3, 4 ];let n = 4;let ans = SubArraySum(arr, n);console.log("Sum of SubArray : " + ans);// This code is contributed by garg28harsh. |
Output
Sum of SubArray : 50
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To solve the problem follow the below idea:
If we take a close look then we observe a pattern.
Let’s take an example:arr[] = [1, 2, 3], n = 3
All subarrays : [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]here first element ‘arr[0]’ appears 3 times
second element ‘arr[1]’ appears 4 times
third element ‘arr[2]’ appears 3 timesEvery element arr[i] appears in two types of subsets:
i) In subarrays beginning with arr[i]. There are
(n-i) such subsets. For example [2] appears
in [2] and [2, 3].ii) In (n-i)*i subarrays where this element is not
first element. For example [2] appears in [1, 2] and [1, 2, 3].Total of above (i) and (ii) = (n-i) + (n-i)*i = (n-i)(i+1)
For arr[] = {1, 2, 3}, sum of subarrays is:
arr[0] * ( 0 + 1 ) * ( 3 – 0 ) +
arr[1] * ( 1 + 1 ) * ( 3 – 1 ) +
arr[2] * ( 2 + 1 ) * ( 3 – 2 )= 1*3 + 2*4 + 3*3
= 20
Follow the below steps to solve the problem:
- Declare an integer answer equal to zero
- Run a for loop for i [0, N]
- Add arr[i] * (i+1) * (N-i) into the answer at each iteration
- Return answer
Below is the implementation of the above approach:
C++
// C++ program to compute sum of// subarray elements#include <bits/stdc++.h>using namespace std;// function compute sum all sub-arraylong int SubArraySum(int arr[], int n){ long int result = 0; // computing sum of subarray using formula for (int i = 0; i < n; i++) result += (arr[i] * (i + 1) * (n - i)); // return all subarray sum return result;}// Driver codeint main(){ int arr[] = { 1, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Sum of SubArray : " << SubArraySum(arr, n) << endl; return 0;} |
Java
// Java program to compute sum of// subarray elementsclass GFG { // function compute sum all sub-array public static long SubArraySum(int arr[], int n) { long result = 0; // computing sum of subarray using formula for (int i = 0; i < n; i++) result += (arr[i] * (i + 1) * (n - i)); // return all subarray sum return result; } /* Driver code */ public static void main(String[] args) { int arr[] = { 1, 2, 3 }; int n = arr.length; System.out.println("Sum of SubArray " + SubArraySum(arr, n)); }}// This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 code to compute# sum of subarray elements# function compute sum# all sub-arraydef SubArraySum(arr, n): result = 0 # computing sum of subarray # using formula for i in range(0, n): result += (arr[i] * (i+1) * (n-i)) # return all subarray sum return result# Driver codearr = [1, 2, 3]n = len(arr)print("Sum of SubArray : ", SubArraySum(arr, n))# This code is contributed by# TheGameOf256. |
C#
// C# program// to compute sum of// subarray elementsusing System;class GFG { // function compute // sum all sub-array public static long SubArraySum(int[] arr, int n) { long result = 0; // computing sum of // subarray using formula for (int i = 0; i < n; i++) result += (arr[i] * (i + 1) * (n - i)); // return all subarray sum return result; } // Driver code static public void Main() { int[] arr = { 1, 2, 3 }; int n = arr.Length; Console.WriteLine("Sum of SubArray: " + SubArraySum(arr, n)); }}// This code is contributed by akt_mit |
PHP
<?php// PHP program to compute // sum of subarray elements//function compute sum all sub-arrayfunction SubArraySum($arr , $n){ $result = 0; // computing sum of subarray // using formula for ($i = 0; $i < $n; $i++) $result += ($arr[$i] * ($i + 1) * ($n - $i)); // return all subarray sum return $result ;}// Driver Code$arr = array(1, 2, 3) ;$n = sizeof($arr);echo "Sum of SubArray : ", SubArraySum($arr, $n) ,"\n";#This code is contributed by aj_36?> |
Javascript
<script>// Efficient Javascript program// to compute sum of subarray elements// Function compute// sum all sub-arrayfunction SubArraySum(arr, n){ let result = 0; // Computing sum of // subarray using formula for(let i = 0; i < n; i++) result += (arr[i] * (i + 1) * (n - i)); // Return all subarray sum return result ;}// Driver codelet arr = [ 1, 2, 3 ];let n = arr.length;document.write("Sum of SubArray : " + SubArraySum(arr, n)); // This code is contributed by divyesh072019</script> |
Output
Sum of SubArray : 20
Time complexity: O(N)
Auxiliary Space: O(1)
This article is contributed by Nishant Singh. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
