Sum of all subarrays of size K
Given an array arr[] and an integer K, the task is to calculate the sum of all subarrays of size K.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 6 9 12 15
Explanation:
All subarrays of size k and their sum:
Subarray 1: {1, 2, 3} = 1 + 2 + 3 = 6
Subarray 2: {2, 3, 4} = 2 + 3 + 4 = 9
Subarray 3: {3, 4, 5} = 3 + 4 + 5 = 12
Subarray 4: {4, 5, 6} = 4 + 5 + 6 = 15Input: arr[] = {1, -2, 3, -4, 5, 6}, K = 2
Output: -1, 1, -1, 1, 11
Explanation:
All subarrays of size K and their sum:
Subarray 1: {1, -2} = 1 – 2 = -1
Subarray 2: {-2, 3} = -2 + 3 = -1
Subarray 3: {3, 4} = 3 – 4 = -1
Subarray 4: {-4, 5} = -4 + 5 = 1
Subarray 5: {5, 6} = 5 + 6 = 11
Naive Approach: The naive approach will be to generate all subarrays of size K and find the sum of each subarray using iteration.
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum // of all subarrays of size K #include <iostream> using namespace std; // Function to find the sum of // all subarrays of size K int calcSum( int arr[], int n, int k) { // Loop to consider every // subarray of size K for ( int i = 0; i <= n - k; i++) { // Initialize sum = 0 int sum = 0; // Calculate sum of all elements // of current subarray for ( int j = i; j < k + i; j++) sum += arr[j]; // Print sum of each subarray cout << sum << " " ; } } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; // Function Call calcSum(arr, n, k); return 0; } |
Java
// Java implementation to find the sum // of all subarrays of size K class GFG{ // Function to find the sum of // all subarrays of size K static void calcSum( int arr[], int n, int k) { // Loop to consider every // subarray of size K for ( int i = 0 ; i <= n - k; i++) { // Initialize sum = 0 int sum = 0 ; // Calculate sum of all elements // of current subarray for ( int j = i; j < k + i; j++) sum += arr[j]; // Print sum of each subarray System.out.print(sum+ " " ); } } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int n = arr.length; int k = 3 ; // Function Call calcSum(arr, n, k); } } // This code is contributed by Rajput-Ji |
C#
// C# implementation to find the sum // of all subarrays of size K using System; class GFG { // Function to find the sum of // all subarrays of size K static void calcSum( int [] arr, int n, int k) { // Loop to consider every // subarray of size K for ( int i = 0; i <= n - k; i++) { // Initialize sum = 0 int sum = 0; // Calculate sum of all elements // of current subarray for ( int j = i; j < k + i; j++) sum += arr[j]; // Print sum of each subarray Console.Write(sum + " " ); } } // Driver Code static void Main() { int [] arr = new int [] { 1, 2, 3, 4, 5, 6 }; int n = arr.Length; int k = 3; // Function Call calcSum(arr, n, k); } } // This code is contributed by shubhamsingh10 |
Python3
# Python3 implementation to find the sum # of all subarrays of size K # Function to find the sum of # all subarrays of size K def calcSum(arr, n, k): # Loop to consider every # subarray of size K for i in range (n - k + 1 ): # Initialize sum = 0 sum = 0 # Calculate sum of all elements # of current subarray for j in range (i, k + i): sum + = arr[j] # Print sum of each subarray print ( sum , end = " " ) # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) k = 3 # Function Call calcSum(arr, n, k) # This code is contributed by mohit kumar 29 |
Javascript
<script> // JavaScript implementation to find the sum // of all subarrays of size K // Function to find the sum of // all subarrays of size K function calcSum(arr, n, k) { // Loop to consider every // subarray of size K for ( var i = 0; i <= n - k; i++) { // Initialize sum = 0 var sum = 0; // Calculate sum of all elements // of current subarray for ( var j = i; j < k + i; j++) sum += arr[j]; // Print sum of each subarray document.write(sum + " " ); } } // Driver Code var arr = [ 1, 2, 3, 4, 5, 6 ]; var n = arr.length; var k = 3; // Function Call calcSum(arr, n, k); </script> |
6 9 12 15
Performance Analysis:
- Time Complexity: As in the above approach, There are two loops, where first loop runs (N – K) times and second loop runs for K times. Hence the Time Complexity will be O(N*K).
- Auxiliary Space Complexity: As in the above approach. There is no extra space used. Hence the auxiliary space complexity will be O(1).
Efficient Approach: Using Sliding Window The idea is to use the sliding window approach to find the sum of all possible subarrays in the array.
- For each size in the range [0, K], find the sum of the first window of size K and store it in an array.
- Then for each size in the range [K, N], add the next element which contributes into the sliding window and subtract the element which pops out from the window.
// Adding the element which // adds into the new window sum = sum + arr[j] // Subtracting the element which // pops out from the window sum = sum - arr[j-k] where sum is the variable to store the result arr is the given array j is the loop variable in range [K, N]
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum // of all subarrays of size K #include <iostream> using namespace std; // Function to find the sum of // all subarrays of size K int calcSum( int arr[], int n, int k) { // Initialize sum = 0 int sum = 0; // Consider first subarray of size k // Store the sum of elements for ( int i = 0; i < k; i++) sum += arr[i]; // Print the current sum cout << sum << " " ; // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Add the element which enters // into the window and subtract // the element which pops out from // the window of the size K sum = (sum - arr[i - k]) + arr[i]; // Print the sum of subarray cout << sum << " " ; } } // Drivers Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; // Function Call calcSum(arr, n, k); return 0; } |
Java
// Java implementation to find the sum // of all subarrays of size K class GFG{ // Function to find the sum of // all subarrays of size K static void calcSum( int arr[], int n, int k) { // Initialize sum = 0 int sum = 0 ; // Consider first subarray of size k // Store the sum of elements for ( int i = 0 ; i < k; i++) sum += arr[i]; // Print the current sum System.out.print(sum+ " " ); // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Add the element which enters // into the window and subtract // the element which pops out from // the window of the size K sum = (sum - arr[i - k]) + arr[i]; // Print the sum of subarray System.out.print(sum+ " " ); } } // Drivers Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int n = arr.length; int k = 3 ; // Function Call calcSum(arr, n, k); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to find the sum # of all subarrays of size K # Function to find the sum of # all subarrays of size K def calcSum(arr, n, k): # Initialize sum = 0 sum = 0 # Consider first subarray of size k # Store the sum of elements for i in range ( k): sum + = arr[i] # Print the current sum print ( sum ,end = " " ) # Consider every subarray of size k # Remove first element and add current # element to the window for i in range (k,n): # Add the element which enters # into the window and subtract # the element which pops out from # the window of the size K sum = ( sum - arr[i - k]) + arr[i] # Print the sum of subarray print ( sum ,end = " " ) # Drivers Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) k = 3 # Function Call calcSum(arr, n, k) # This code is contributed by chitranayal |
C#
// C# implementation to find the sum // of all subarrays of size K using System; class GFG{ // Function to find the sum of // all subarrays of size K static void calcSum( int []arr, int n, int k) { // Initialize sum = 0 int sum = 0; // Consider first subarray of size k // Store the sum of elements for ( int i = 0; i < k; i++) sum += arr[i]; // Print the current sum Console.Write(sum+ " " ); // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Add the element which enters // into the window and subtract // the element which pops out from // the window of the size K sum = (sum - arr[i - k]) + arr[i]; // Print the sum of subarray Console.Write(sum + " " ); } } // Drivers Code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6 }; int n = arr.Length; int k = 3; // Function Call calcSum(arr, n, k); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation to find the sum // of all subarrays of size K // Function to find the sum of // all subarrays of size K function calcSum(arr, n, k) { // Initialize sum = 0 var sum = 0; // Consider first subarray of size k // Store the sum of elements for ( var i = 0; i < k; i++) sum += arr[i]; // Print the current sum document.write( sum + " " ); // Consider every subarray of size k // Remove first element and add current // element to the window for ( var i = k; i < n; i++) { // Add the element which enters // into the window and subtract // the element which pops out from // the window of the size K sum = (sum - arr[i - k]) + arr[i]; // Print the sum of subarray document.write( sum + " " ); } } // Drivers Code var arr = [ 1, 2, 3, 4, 5, 6 ]; var n = arr.length; var k = 3; // Function Call calcSum(arr, n, k); // This code is contributed by noob2000. </script> |
6 9 12 15
Performance Analysis:
- Time Complexity: As in the above approach. There is one loop which take O(N) time. Hence the Time Complexity will be O(N).
- Auxiliary Space Complexity: As in the above approach. There is no extra space used. Hence the auxiliary space complexity will be O(1).
Related Topic: Subarrays, Subsequences, and Subsets in Array