Find Sum (i … j) in a list

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

Problem

Let there be a list . Then the function is defined as follows:

for

we need to make

runtime solution

This is a straight forward solution which simply starts adding the numbers in the list from the i^th index to j^th 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;
}

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 time. We need an additional array of length (n + 1) to hold the preprocessed data. The preprocessed list is defined as follows.

where

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 time, and the additional space taken by the preprocess list takes memory.

To retrieve the from the preprocessed array we need to perform the following operation:

where

For example lets take the list . Then the preprocessed list will be

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

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.