Sum of all odd length subarrays
Given an array arr[] consisting of N integers, the task is to find the sum of all the elements of all possible subarrays of odd length.
Examples:
Input: arr[] = {3, 2, 4}
Output: 18
Explanation:
The odd length subarrays along with their sum are as follows:
1) {3} = sum is 3.
2) {2} = sum is 2.
3) {4} = sum is 4.
4) {3, 2, 4} = sum is 3 + 2 + 4 = 9.
Therefore, sum of all subarrays = 3 + 2 + 4 + 9 = 18.Input: arr[] = {1, 2, 1, 2}
Output: 15
Explanation:
The odd length subarrays along with their sum are as follows:
1) {1} = sum is 1.
2) {2} = sum is 2.
3) {1} = sum is 1.
4) {2} = sum is 2.
5) {1, 2, 1} = sum is 1 + 2 + 1 = 4.
6) {2, 1, 2} = sum is 2 + 1 + 2 = 5.
Therefore, sum of all subarrays = 1 + 2 + 1 + 2 + 4 + 5 = 15.
Naive Approach: The simplest approach is to generate all possible subarrays of odd length from the given array and find the sum of all such subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the sum // of all odd length subarrays int OddLengthSum(vector< int >& arr) { // Stores the sum int sum = 0; // Size of array int l = arr.size(); // Traverse the array for ( int i = 0; i < l; i++) { // Generate all subarray of // odd length for ( int j = i; j < l; j += 2) { for ( int k = i; k <= j; k++) { // Add the element to sum sum += arr[k]; } } } // Return the final sum return sum; } // Driver Code int main() { // Given array arr[] vector< int > arr = { 1, 5, 3, 1, 2 }; // Function Call cout << OddLengthSum(arr); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.Arrays; class GFG{ // Function to calculate the sum // of all odd length subarrays static int OddLengthSum( int [] arr) { // Stores the sum int sum = 0 ; // Size of array int l = arr.length; // Traverse the array for ( int i = 0 ; i < l; i++) { // Generate all subarray of // odd length for ( int j = i; j < l; j += 2 ) { for ( int k = i; k <= j; k++) { // Add the element to sum sum += arr[k]; } } } // Return the final sum return sum; } // Driver Code public static void main (String[] args) { // Given array arr[] int [] arr = { 1 , 5 , 3 , 1 , 2 }; // Function call System.out.print(OddLengthSum(arr)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to calculate the sum # of all odd length subarrays def OddLengthSum(arr): # Stores the sum sum = 0 # Size of array l = len (arr) # Traverse the array for i in range (l): # Generate all subarray of # odd length for j in range (i, l, 2 ): for k in range (i, j + 1 , 1 ): # Add the element to sum sum + = arr[k] # Return the final sum return sum # Driver Code # Given array arr[] arr = [ 1 , 5 , 3 , 1 , 2 ] # Function call print (OddLengthSum(arr)) # This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate the sum // of all odd length subarrays static int OddLengthSum( int [] arr) { // Stores the sum int sum = 0; // Size of array int l = arr.Length; // Traverse the array for ( int i = 0; i < l; i++) { // Generate all subarray of // odd length for ( int j = i; j < l; j += 2) { for ( int k = i; k <= j; k++) { // Add the element to sum sum += arr[k]; } } } // Return the final sum return sum; } // Driver Code public static void Main () { // Given array arr[] int [] arr = { 1, 5, 3, 1, 2 }; // Function call Console.Write(OddLengthSum(arr)); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // javascript program for the above approach // Function to calculate the sum // of all odd length subarrays function OddLengthSum(arr) { // Stores the sum var sum = 0; // Size of array var l = arr.length; // Traverse the array for ( var i = 0; i < l; i++) { // Generate all subarray of // odd length for ( var j = i; j < l; j += 2) { for ( var k = i; k <= j; k++) { // Add the element to sum sum += arr[k]; } } } // Return the final sum return sum; } // Driver Code // Given array arr[] var arr = [ 1, 5, 3, 1, 2 ] // Function call document.write(OddLengthSum(arr)); // This code is contributed by bunnyram19. </script> |
48
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to observe the following pattern after generating all the subarrays of odd length:
- For any element at index idx there are (idx + 1) choices on the left side of it and (N – idx) choices on the right side of it.
- Therefore, for any element arr[i], the count of arr[i] is (i + 1) * (N – i) in all the subarrays.
- So, for an element arr[i], there are ((i + 1) * (N – i) + 1) / 2 sub-arrays with odd length.
- Finally, arr[i] will have a total of ((i + 1) * (n – i) + 1) / 2 frequency in the sum.
Therefore, to find the sum of all elements of all the subarrays of odd length, the idea is to iterate over the array and for every ith array element, add [((i + 1) * (n – i) + 1) / 2]*arr[i] to the sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that finds the sum of all // the element of subarrays of odd length int OddLengthSum(vector< int >& arr) { // Stores the sum int sum = 0; // Size of array int l = arr.size(); // Traverse the given array arr[] for ( int i = 0; i < l; i++) { // Add to the sum for each // contribution of the arr[i] sum += (((i + 1) * (l - i) + 1) / 2) * arr[i]; } // Return the final sum return sum; } // Driver Code int main() { // Given array arr[] vector< int > arr = { 1, 5, 3, 1, 2 }; // Function Call cout << OddLengthSum(arr); return 0; } |
Java
// Java program for the above approach class GFG{ // Function that finds the sum of all // the element of subarrays of odd length static int OddLengthSum( int []arr) { // Stores the sum int sum = 0 ; // Size of array int l = arr.length; // Traverse the given array arr[] for ( int i = 0 ; i < l; i++) { // Add to the sum for each // contribution of the arr[i] sum += (((i + 1 ) * (l - i) + 1 ) / 2 ) * arr[i]; } // Return the final sum return sum; } // Driver Code public static void main(String[] args) { // Given array arr[] int []arr = { 1 , 5 , 3 , 1 , 2 }; // Function call System.out.print(OddLengthSum(arr)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function that finds the sum of all # the element of subarrays of odd length def OddLengthSum(arr): # Stores the sum Sum = 0 # Size of array l = len (arr) # Traverse the given array arr[] for i in range (l): # Add to the sum for each # contribution of the arr[i] Sum + = ((((i + 1 ) * (l - i) + 1 ) / / 2 ) * arr[i]) # Return the final sum return Sum # Driver code # Given array arr[] arr = [ 1 , 5 , 3 , 1 , 2 ] # Function call print (OddLengthSum(arr)) # This code is contributed by divyeshrabadiya07 |
C#
// C# program for // the above approach using System; class GFG{ // Function that finds the // sum of all the element of // subarrays of odd length static int OddLengthSum( int []arr) { // Stores the sum int sum = 0; // Size of array int l = arr.Length; // Traverse the given array []arr for ( int i = 0; i < l; i++) { // Add to the sum for each // contribution of the arr[i] sum += (((i + 1) * (l - i) + 1) / 2) * arr[i]; } // Return the readonly sum return sum; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = {1, 5, 3, 1, 2}; // Function call Console.Write(OddLengthSum(arr)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to implement // the above approach // Function that finds the sum of all // the element of subarrays of odd length function OddLengthSum(arr) { // Stores the sum let sum = 0; // Size of array let l = arr.length; // Traverse the given array arr[] for (let i = 0; i < l; i++) { // Add to the sum for each // contribution of the arr[i] sum += Math.floor(((i + 1) * (l - i) + 1) / 2) * arr[i]; } // Return the final sum return sum; } // Driver Code // Given array arr[] let arr = [ 1, 5, 3, 1, 2 ]; // Function call document.write(OddLengthSum(arr)); // This code is contributed by target_2. </script> |
48
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us