Find Sum (i … j) in a list


The problem is to sum the ith to jth element of a given list. The easiest solution runs in \mathcal{O}(n) time, which starts are the ith index and adds up the numbers in the list until it reaches the jth index. In this post i will show the process of calculating the sum of elements i through j both inclusive (where i \le j), which takes \mathcal{O}(1) time for finding the sum, and \mathcal{O}(n) time and space for preprocessing the given list of length n.

Problem

Let there be a list x_0, x_1, \ldots, x_n. Then the function sum (i, j) is defined as follows:

sum (i, j) = x_i + x_{i+1} + \ldots + x_{j-1} + x_j for i \le j \le n

we need to make sum (i, j)

\mathcal{O}(n) runtime solution

This is a straight forward solution which simply starts adding the numbers in the list from the ith index to jth index.

Sourcecode

The function for this process is shown below


/* Return the sum (i, j). Takes O(1) time
 */
int
sum (int i, int j, int *list)
{
  int s = 0;
  
  while (i<=j)
  {
	s += list[i];
	i++;
  }
  return s;
}

\mathcal{O}(1) runtime solution

In this case we need an auxiliary array in which we do a simple preprocessing on the given list and store. Using this preprocessed list we find the required sum in \mathcal{O}(1) time. We need an additional array of length (n + 1) to hold the preprocessed data. The preprocessed p list is defined as follows.

p_{i}=\sum_{j=0}^{i-1}x_{i} where 0 \le i \le n+1

that is:

p[0] = 0
p[1] = x[0]
p[2] = x[0] + x[1]
p[3] = x[0] + x[1] + x[2]
              .
              .
              .
p[n + 1] = x[0] + x[1] + x[2] + ... + x[n]

This process takes \mathcal{O}(n) time, and the additional space taken by the preprocess list takes \mathcal{O}(n) memory.

To retrieve the sum (i, j) from the preprocessed array we need to perform the following operation:

sum (i, j) = p_{j+1} - p_i where 0 \le i \le j \le n

For example lets take the list x_0, x_1, x_2, x_3, x_4. Then the preprocessed list will be

p_0 = 0
p_1 = x_0
p_2 = x_0 + x_1
p_3 = x_0 + x_1 + x_2
p_4 = x_0 + x_1 + x_2 + x_3
p_5 = x_0 + x_1 + x_2 + x_3 + x_4

And example of the sum of the elements 1 through 3 (both inclusive) will be:

sum (1, 3) = p_4 - p_1 = (x_0 + x_1 + x_2 + x_3) - (x_0) = x_1 + x_2 + x_3

Sourcecode

#include <stdio.h>
#include <stdlib.h>

/* Function to make the preprocess list from the input list
 * This takes O(n) time.
 */
void
preprocess_list (int *list, int n, int *preprocess)
{
  int i, s = 0;

  for (i = 0; i <= n; i++)
    {
      preprocess[i] = s;
      s += list[i];
    }
}

/* Return the sum (i, j). Takes O(1) time
 */
int
sum (int i, int j, int *preprocess, int n)
{
  if ((i > j) || (i >= n) || (j >= n) || (i < 0) || (j < 0))
    {
      return 0x7eadbeef;
    }
  return preprocess[j + 1] - preprocess[i];
}

/* Driver function to demonstrate the sum (i, j) function.
 */
int
main (void)
{
  int *list, n, *preprocess;
  int i, j, k;

  printf ("\nEnter list elements: ");
  scanf (" %d", &n);

  list = malloc (sizeof (int) * n);
  preprocess = malloc (sizeof (int) * n);

  printf ("\nEnter the list elements: ");
  for (k = 0; k < n; k++)
    {
      scanf (" %d", &list[k]);
    }

  preprocess_list (list, n, preprocess);

  /* Enter out of bounds index to exit the program */
  while (1)
    {
      printf ("\n\nTo get sum (i, j) Enter i, j: ");
      scanf (" %d %d", &i, &j);

      if ((i < n) && (j < n) && (i >= 0) && (j >= 0))
        {
          printf ("\nsum (%d, %d) = %d", i, j, sum (i, j, preprocess, n));
        }
      else
        {
          printf ("\nIndex out of bounds. quit.");
          break;
        }
    }

  free (list);
  free (preprocess);

  printf ("\n");
  return 0;
}

Sample Output

Enter list elements: 5

Enter the list elements: 1 2 3 -4 5


To get sum (i, j) Enter i, j: 1 3

sum (1, 3) = 1

To get sum (i, j) Enter i, j: 0 4

sum (0, 4) = 7

To get sum (i, j) Enter i, j: 3 1  

sum (3, 1) = 0

To get sum (i, j) Enter i, j: -1 0

Index out of bounds. quit.
About these ads

About phoxis

Homo-sapiens
This entry was posted in Coding Discussions, Computer Science and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s