Given an array arr[ ] containing integers only and an odd number sum. The goal is to create a sum array arr_2[ ] such each arr_2[i] is the sum of previous sum/2 elements of arr[] + arr[i] + next sum/2 elements of arr[]. If sum is 1 then arr_2[i]=arr[i]
For Example
Input
arr[] = { 4, 1, 7, 5, 2, 9} sum=3Output
Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3
Explanation
The sum array is constructed as: arr_2[0]=arr[0]+arr[1] = 4+1 = 5 arr_2[1]=arr[0]+arr[1]+arr[2] = 4+1+7 = 12 arr_2[2]=arr[1]+arr[2]+arr[3] = 1+7+5 = 13 arr_2[3]=arr[2]+arr[3]+arr[4] = 7+5+2 = 14 arr_2[4]=arr[3]+arr[4]+arr[5] = 5+2+9 = 16 arr_2[5]=arr[4]+arr[5] = 2+9 = 11s
Input
arr[] = { 1,2,3,4,5 } sum=5Output
Construction of sum-array with sum of elements in given range are − 6 10 15 14 12
Explanation
The sum array is constructed as: arr_2[0]=arr[0]+arr[1]+arr[2] = 1+2+3 = 6 arr_2[1]=arr[0]+arr[1]+arr[2]+arr[3] = 1+2+3+4= 10 arr_2[2]=arr[0]+arr[1]+arr[2]+arr[3]+arr[4] = 1+2+3+4+5 = 15 arr_2[3]=arr[1]+arr[2]+arr[3]+arr[4] = 2+3+4+5= 14 arr_2[4]=arr[2]+arr[3]+arr[4]= 3+4+5 = 12
Approach used in the below program is as follows −
In this approach we will use the sliding window concept. Add the next rightmost element to the previous window sum and remove the leftmost element from that.
Take an integer array arr[] and a value sum as input.
Function sum_array(int arr[], int size, int sum) returns the sum-array with sum of elements in the given range.
Take the initial count as 0.
Take the sum array as arr_2[size].
Take temp = sum / 2 + 1.
Add temp number of elements from 0 to temp to count. And set arr_2[0] as count.
For next elements of sum array, traverse using for loop from i=1 to i<size.
Take temp_1 = i − (sum / 2) − 1. If it is >=0 then subtract arr[temp_1] from count.
Take temp_2 = i + (sum / 2). If it is < size then add arr[temp_2] to count.
Set arr_2[i] = count.
At the end of for loop we will have arr_2[] as a sum array.
Print the sum array arr_2[] using for loop.
Example
#include <bits/stdc++.h>
using namespace std;
void sum_array(int arr[], int size, int sum){
int count = 0;
int arr_2[size];
int temp = sum / 2 + 1;
for (int i = 0; i < temp; i++){
count = count + arr[i];
}
arr_2[0] = count;
for (int i = 1; i < size; i++){
int temp_1 = i − (sum / 2) − 1;
if (temp_1 >= 0){
count = count − arr[temp_1];
}
int temp_2 = i + (sum / 2);
if (temp_2 < size){
count = count + arr[temp_2];
}
arr_2[i] = count;
}
cout<<"Construction of sum−array with sum of elements in given range are: ";
for (int i = 0; i < size; i++){
cout<< arr_2[i] << " ";
}
}
int main(){
int arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 };
int sum = 3;
int size = sizeof(arr) / sizeof(int);
sum_array(arr, size, sum);
return 0;
}Output
If we run the above code it will generate the following output −
Construction of sum-array with sum of elements in given range are − 5 12 13 14 16 17 17 9 3