Sum of all Subarrays | Set 1
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-array long 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 code int 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 elements 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(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-array def 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 code arr = [ 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 elements using 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-array function 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> |
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 array 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 ll 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 elements 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) { 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 elements class 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 system using System; // C# program to compute sum of // subarray elements public 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-array function 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. |
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-array long 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 code int 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 elements 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 */ 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-array def 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 code arr = [ 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 elements using 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-array function 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-array function 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 code let arr = [ 1, 2, 3 ]; let n = arr.length; document.write( "Sum of SubArray : " + SubArraySum(arr, n)); // This code is contributed by divyesh072019 </script> |
Sum of SubArray : 20
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us