综合编程

Sum of all subarrays of size K

微信扫一扫,分享到朋友圈

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: {1, 2, 3} = 3 + 4 + 5 = 12

Subarray 4: {1, 2, 3} = 4 + 5 + 6 = 15

Input: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


Recommended: Please try your approach on

{IDE}


first, before moving on to the solution.

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++

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ implementaion 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;
}

chevron_right

filter_none

Output:

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)
    .


Effiecient Approach: Using Sliding Window

The idea is to use thesliding 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++

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ implementaion 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 substract
  
// 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;
}

chevron_right

filter_none

Output:

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)
    .

My Personal Notes

arrow_drop_up

Recommended Posts:

云米:4Q19营收17.417亿元 同比增长82.2%

上一篇

HTTP2.0学习 与 Nginx和Tomcat配置HTTP2.0

下一篇

你也可能喜欢

评论已经被关闭。

插入图片

热门栏目

Sum of all subarrays of size K

长按储存图像,分享给朋友