May 122017
 

This question is from exercise in my book Dynamic Programming for Coding Interviews (Question: 1.2, Page-5)

Question: Given an array, arr of integers, write a recursive function that add sum of all the previous numbers to each index of the array. For example, if the input array is

{1, 2, 3, 4, 5, 6}

then your function should update the array to

{1, 3, 6, 10, 15, 21}


Iterative Solution:

First, let us look at the non-recursive solution. We are adding all the previous elements to each element in the array, but the solution does not require two loops. By the time we reach arr[i], arr[i-1] already stores the sum of all elements from 0 to i-1. So we just need to add arr[i-1] to arr[i] as shown below:

void addPrev(int* arr, int n)
{
   for(int i=1; i<n; i++)
   {
      arr[i] += arr[i-1];
   }
}

The above code takes O(n) time visiting each element only once.

Recursive Solution:

In the recursive solution we can either move forward (bottom-up) or backward (top-down). Lets look at the two solutions

1. Solve the problem for first n-1 elements (using recursion). Once the problem is solved for first n-1 elements, we just need to add the value of (n-1)’th to the n’th element.

void addPrevRec1(int *arr, int n)
{
    // TERMINATING CONDITION.
    // if we are first element, don't do anything
    if(n<=1){ return; }
    
    // Add all prev elements for first n-1 elements
    addPrevRec1(arr, n-1);
    
    // With problem solved till (n-1),
    // we just need to add (n-1)th element to n'th element
    arr[n-1] += arr[n-2];
}

Above approach is using head recursion. We can also try to use tail recursion, where we first solve it to i’th index and then ask the recursion to solve it for rest of the array. In this case we need to pass one extra element (either the index, sum or some other value). Let us say, we are passing, sum of all previous elements to be added to the next element. Initial value of sum should be 0 (because nothing need to be added to arr[0].

void addPrevRec2(int *arr, int n, int sum=0)
{
    // TERMINATING CONDITION. No element in array
    if(n==0){ return; }
    
    // Add previous element's sum to first element
    arr[0] += sum;
    
    // To the next element, we need to add arr[0]
    addPrevRec2(arr+1, n-1, arr[0]);
}

Both the recursive solution takes O(n) time and O(n) extra memory, because there will be O(n) Activation records (stack frames) of recursive functions.

vliegen123.nl

  2 Responses to “Add sum of all previous elements in array (DPFCI_1.2)”

Comments (2)
  1. Your tail recursion looks incorrect. You have only updated arr[0] where are rest indices updated.

    • It should be some thing like this:
      Called something like this:
      SumArray(arr,0,n,sum)

      SumArray(arr,i,n,sum)
      {

      if(i==n) return;

      arr[i]= arr[i]+sum;
      SumArray (arr,i+1, n, arr[i]);
      }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)