Write Java and C programs to implement prefixes averages algorithm.

Prefix Average Problem: Sometimes it is useful to know the "prefix average" of a set of values. For an example, if you are an extravagant person and wonder what the average expenses you make each day for a given month. You may keep an array of everyday expenses like:

------------------------------------ 
| 500 | 400 | 600 | 350 | 470 | ... 
------------------------------------

If you also want to keep track of the "daily average" of your expenses for each day of the month, you can simply compute the average of all the days up-to and including the day you want the average for. For example, on day 1 there have 500 bucks been spent. The average expenses per day will be the total expenses (500) divided by the number of days (1) for an average of 1 in day. By day 3 the daily average has changed substantially: a total of 1500 bucks have been spent (500+400+600) over the course of 3 days, giving a daily average of 500 in day.

This computation is known as the prefix average. It averages all the "previous" values. Usually it is used to find the prefix average for every location in an array. Prefix average is very useful in financial analysis applications.

Here, we develop C and Java program to compute prefix averages of an array. We develop a method computePrefixAvg that takes an array arr storing n integers, where n >= 1 and returns an array containing prefix averages of the array passed to computePrefixAvg. Function computePrefixAvg runs in linear time.

Following are the Java and C codes respectively to compute prefix averages of an array.

Java code for prefix averages problem.

class PrefixAverage
{
  public static void main(String[] args)
  {
    int arr[] = {12, 14, 13, 15, 19, 17, 16, 11, 18, 20};
    int pfavg[], i, j, k; 
 
    pfavg = computePrefixAvg(arr);
 
    System.out.println("Array Elements              Average");
    System.out.println("===================================");
    for (i = 0; i < 10; i ++ )
    {
      for (j = 0; j <= i; j++)
      {
        System.out.print(arr[j] + " ");
      }
      for (k = 10; k > j; k--)
      {
        System.out.print("   ");
      }
      System.out.println(" : " + pfavg[i]);
    }  
  }
 
  static int[] computePrefixAvg(int arr[])
  {
    int length = arr.length;
    int[] pfArr = new int[length];
    int sum = 0;
 
    for(int i = 0; i < length; i++)
    {
      sum += arr[i];
      pfArr[i] = sum / (i + 1);
    }
 
    return pfArr;
  }
}
 
OUTPUT
======
D:\JavaPrograms>javac PrefixAverage.java
 
D:\JavaPrograms>java PrefixAverage
Array Elements              Average
===================================
12                             : 12
12 14                          : 13
12 14 13                       : 13
12 14 13 15                    : 13
12 14 13 15 19                 : 14
12 14 13 15 19 17              : 15
12 14 13 15 19 17 16           : 15
12 14 13 15 19 17 16 11        : 14
12 14 13 15 19 17 16 11 18     : 15
12 14 13 15 19 17 16 11 18 20  : 15

C code for prefix averages problem.

#include <stdio.h>
#define SIZE 10
 
void computePrefixAvg(int*, int*);
 
int main()
{
  int arr[] = {12, 14, 13, 15, 19, 17, 16, 11, 18, 20};
  int pfavg[SIZE], i, j, k; 
 
  computePrefixAvg(arr, pfavg);
 
  printf("Array Elements              Average\n");
  printf("===================================\n");
  for (i = 0; i < 10; i ++ )
  {
    for (j = 0; j <= i; j++)
    {
	  printf("%d ", arr[j]);
    }
    for (k = 10; k > j; k--)
    {
	  printf("   ");
    }
    printf(" : %d\n", pfavg[i]);
  }  
}
 
void computePrefixAvg(int* arr, int* pfArr)
{
  int sum = 0;
 
  for(int i = 0; i < SIZE; i++)
  {
    sum += arr[i];
    pfArr[i] = sum / (i + 1);
  }
}
 
OUTPUT
======
Array Elements              Average
===================================
12                             : 12
12 14                          : 13
12 14 13                       : 13
12 14 13 15                    : 13
12 14 13 15 19                 : 14
12 14 13 15 19 17              : 15
12 14 13 15 19 17 16           : 15
12 14 13 15 19 17 16 11        : 14
12 14 13 15 19 17 16 11 18     : 15
12 14 13 15 19 17 16 11 18 20  : 15

Hope you have enjoyed reading C and Java programs for prefix averages proble. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!




Get Free Tutorials by Email

About the Author

is the main author for cs-fundamentals.com. He is a software professional (post graduated from BITS-Pilani) and loves writing technical articles on programming and data structures.

Today's Tech News

Amazon resists Echo murder evidence callPosted on Thursday February 23, 2017

Amazon issues formal legal response to requests to hand over information from its smart speaker Echo.

Router hacker suspect arrested at Luton AirportPosted on Thursday February 23, 2017

The "mastermind" behind a massive 2016 attack may face sabotage charges in Germany.

A guided tour of the cybercrime undergroundPosted on Wednesday February 22, 2017

Malware researcher Anton talks about who does what in the web's dark marketplaces.

Courtesy BBC News