Partial Sums For Arrays

In this blog, you will learn about partial Sums for Arrays.

Problem Statement

Add the numbers between the lower index and upper index in an array

Inputs

1. A random array of both positive numbers and negative numbers.
2. The function should accept two parameters namely, the Lower index and the Upper index.

Example

let's consider the below inputs and try to understand the solution.

arr = [3, 5, 6, 7, 2, -4, 10, 8];
lowerIndex = 1;
upperindex = 6;

Solution 1

Code Snippet

var sum = 0;
for (int i = 0; i < arr.length; i++) // n = end of the array
{
     if(i <= 1 && i>=5)
     {
        sum =+ arr[i];
     }
}

Approach

1. Iterate the complete array.
2. Check the index using the if condition if it's within the specified lower and upper indexes.
3. Add the numbers to the sum variable.
4. The complexity of this implementation is O(n)

Solution 2

Code Snippet

var sum = 0;
for (int i = lowerIndex; i <= upperIndex; i++) 
{
    sum =+ arr[i];
}

Approach

1. Iterate the array between the lower index and upper index only.
2. Add the numbers to the sum variable.
3. Complexity of this implementation is O(log(n))

Solution 3

I am still working on it for a very big array and multiple iterations of the function call — to make it for O(1) for the consecutive iterations.