Construct sum-array with sum of elements in given range

0 0 6 minutes read

You are given an array of n-elements and an odd-integer m. You have to construct a new sum_array from given array such that sum_array[i] = ?arr[j] for (i-(m/2)) < j (i+(m/2)).

note : for 0 > j or j >= n take arr[j] = 0.

Examples:

Input : arr[] = {1, 2, 3, 4, 5}, 
            m = 3
Output : sum_array = {3, 6, 9, 12, 9}
Explanation : sum_array[0] = arr[0] + arr[1]
     sum_array[1] = arr[0] + arr[1] + arr[2]
     sum_array[2] = arr[1] + arr[2] + arr[3]
     sum_array[3] = arr[2] + arr[3] + arr[4]
     sum_array[4] = arr[3] + arr[4]

Input : arr[] = {2, 4, 3, 4, 2}, 
           m = 1
Output : sum_array = {2, 4, 3, 4, 2}
Explanation : sum_array[0] = arr[0] 
              sum_array[1] = arr[1]
              sum_array[2] = arr[2]
              sum_array[3] = arr[3]
              sum_array[4] = arr[4]

Basic Approach : As per problem statement, we calculate sum_array[i] by iterating over i-(m/2) to i+(m/2). According to this approach, we have a nested loop which will result into time complexity of O(n*m).
Efficient Approach : For calculating sum_array is to use sliding window concept and thus can easily save our time. For Sliding window, the time complexity is O(n).

Algorithm

calculate sum of first (m/2)+1 elementssum_array[0] = sumfor i=1 to i<nif( (i-(m/2)-1) >= 0 )
           sum -= arr[(i-(m/2)-1)]if( (i+m/2) < n)
           sum += arr[(i+m/2)]sum_array[i] = sumprint sum_array

Implementation:

C++

// CPP Program to find sum array for a given
// array.
#include <bits/stdc++.h>
using namespace std;
 
// function to calc sum_array and print
void calcSum_array(int arr[], int n, int m)
{
    int sum = 0;
    int sum_array[n];
 
    // calc 1st m/2 + 1 element for 1st window
    for (int i = 0; i < m / 2 + 1; i++)
        sum += arr[i];
    sum_array[0] = sum;
 
    // use sliding window to
    // calculate rest of sum_array
    for (int i = 1; i < n; i++) {
        if (i - (m / 2) - 1 >= 0)
            sum -= arr[i - (m / 2) - 1];
        if (i + (m / 2) < n)
            sum += arr[i + (m / 2)];
        sum_array[i] = sum;
    }
 
    // print sum_array
    for (int i = 0; i < n; i++)
        cout << sum_array[i] << " ";
}
 
// driver program
int main()
{
    int arr[] = { 3, 6, 2, 7, 3, 8, 4, 
                      9, 1, 5, 0, 4 };
    int m = 5;
    int n = sizeof(arr) / sizeof(int);
    calcSum_array(arr, n, m);
    return 0;
}

Java

// Java Program to find sum array 
// for a given array.
class GFG 
{
    // function to calc sum_array and print
    static void calcSum_array(int arr[], int n, int m)
    {
        int sum = 0;
        int sum_array[] = new int[n];
     
        // calc 1st m/2 + 1 element
        // for 1st window
        for (int i = 0; i < m / 2 + 1; i++)
            sum += arr[i];
        sum_array[0] = sum;
     
        // use sliding window to
        // calculate rest of sum_array
        for (int i = 1; i < n; i++) 
        {
            if (i - (m / 2) - 1 >= 0)
                sum -= arr[i - (m / 2) - 1];
            if (i + (m / 2) < n)
                sum += arr[i + (m / 2)];
            sum_array[i] = sum;
        }
     
        // print sum_array
        for (int i = 0; i < n; i++)
            System.out.print(sum_array[i] + " ");
    }
     
    // Driver program
    public static void main(String[] args)
    {
        int arr[] = { 3, 6, 2, 7, 3, 8, 4, 9, 1, 5, 0, 4 };
        int m = 5;
        int n = arr.length;
        calcSum_array(arr, n, m);
    }
}
 
// This code is contributed by prerna saini.

Python3

# Python3 Program to find Sum array 
# for a given array.
import math as mt
 
# function to calc Sum_array and print
def calcSum_array(arr, n, m):
 
    Sum = 0
    Sum_array = [0 for i in range(n)]
 
    # calc 1st m/2 + 1 element for 1st window
    for i in range(m // 2 + 1):
        Sum += arr[i]
    Sum_array[0] = Sum
 
    # use sliding window to
    # calculate rest of Sum_array
    for i in range(1, n):
        if (i - (m // 2) - 1 >= 0):
            Sum -= arr[i - (m // 2) - 1]
        if (i + (m / 2) < n):
            Sum += arr[i + (m //2)]
        Sum_array[i] = Sum
     
    # print Sum_array
    for i in range(n):
        print(Sum_array[i], end = " ")
 
# Driver Code
arr = [ 3, 6, 2, 7, 3, 8, 4, 9, 1, 5, 0, 4 ]
m = 5
n = len(arr)
calcSum_array(arr, n, m)
 
# This code is contributed by mohit kumar 29

C#

// C# Program to find sum array 
// for a given array.
using System;
 
class GFG 
{
    // function to calc sum_array and print
    static void calcSum_array(int []arr, int n, int m)
    {
        int sum = 0;
        int []sum_array = new int[n];
     
        // calc 1st m/2 + 1 element
        // for 1st window
        for (int i = 0; i < m / 2 + 1; i++)
            sum += arr[i];
        sum_array[0] = sum;
     
        // use sliding window to
        // calculate rest of sum_array
        for (int i = 1; i < n; i++) 
        {
            if (i - (m / 2) - 1 >= 0)
                sum -= arr[i - (m / 2) - 1];
            if (i + (m / 2) < n)
                sum += arr[i + (m / 2)];
            sum_array[i] = sum;
        }
     
        // print sum_array
        for (int i = 0; i < n; i++)
        Console.Write(sum_array[i] + " ");
    }
     
    // Driver program
    public static void Main()
    {
        int []arr = { 3, 6, 2, 7, 3, 8, 4, 9, 1, 5, 0, 4 };
        int m = 5;
        int n = arr.Length;
        calcSum_array(arr, n, m);
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find sum array 
// for a given array.
 
// function to calc sum_array and print
function calcSum_array(&$arr, $n, $m)
{
    $sum = 0;
    $sum_array = array();
 
    // calc 1st m/2 + 1 element
    // for 1st window
    for ($i = 0; 
         $i < (int)($m / 2) + 1; $i++)
        $sum = $sum + $arr[$i];
    $sum_array[0] = $sum;
 
    // use sliding window to
    // calculate rest of sum_array
    for ($i = 1; $i < $n; $i++) 
    {
        if ($i - (int)($m / 2) - 1 >= 0)
            $sum = $sum - $arr[$i - 
                    (int)($m / 2) - 1];
        if ($i + (int)($m / 2) < $n)
            $sum = $sum + $arr[$i + 
                    (int)($m / 2)];
        $sum_array[$i] = $sum;
    }
 
    // print sum_array
    for ($i = 0; $i < $n; $i++)
        echo $sum_array[$i] . " ";
}
 
// Driver Code
$arr = array(3, 6, 2, 7, 3, 8, 
             4, 9, 1, 5, 0, 4 );
$m = 5;
$n = sizeof($arr);
calcSum_array($arr, $n, $m);
 
// This code is contributed by Mukul Singh
?>

Javascript

<script>
// JavaScript Program to find sum array for a given
// array.
 
// function to calc sum_array and print
function calcSum_array(arr, n, m)
{
    let sum = 0;
    let sum_array = new Array(n);
 
    // calc 1st m/2 + 1 element for 1st window
    for (let i = 0; i < Math.floor(m / 2) + 1; i++)
        sum += arr[i];
    sum_array[0] = sum;
 
    // use sliding window to
    // calculate rest of sum_array
    for (let i = 1; i < n; i++)
    {
        if (i - Math.floor(m / 2) - 1 >= 0)
            sum -= arr[i - Math.floor(m / 2) - 1];
        if (i + Math.floor(m / 2) < n)
            sum += arr[i + Math.floor(m / 2)];
        sum_array[i] = sum;
    }
 
    // print sum_array
    for (let i = 0; i < n; i++)
        document.write(sum_array[i] + " ");
}
 
// Driver program
 
    let arr = [ 3, 6, 2, 7, 3, 8, 4,
                    9, 1, 5, 0, 4 ];
    let m = 5;
    let n = arr.length;
    calcSum_array(arr, n, m);
 
// This code is contributed by Surbhi Tyagi.
</script>

Output

11 18 21 26 24 31 25 27 19 19 10 9

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!