Java Array Advice

Question

I'm doing a practice problem and I'm stuck. The question is

"Given an array a of n numbers (say doubles), consider the problem of computing the average of the first i numbers, for i ranging from 0 to n-1. That is, compute the array b of length n, where b[i] = a[0] + a[1] ....+ a[i]/(i + 1) for 0 <= i < n. Write a Java program to solve this problem. Your program can generate its own array, for example a[i] = i + 1. See how large an array you can process in less than 5 seconds. (For full credit it should be at least one million.) Characterize the time complexity of your algorithm."

Here is my attempt at solving it:

public class largeArray{

public static void main(String[] args){

  double[] aa = new double[1000000];
  System.out.println(CalculateAvg(aa));




}
public static double CalculateAvg(double[] a){
  int i =0;
  double[] array = new double[i];
  a[i] = i + 1;

  for(int k=0; k<array.length; i++){
     double total = a[k]+a[k];
     double sum = ((total)/a[i]);
  }

 return a[i];
 }
}

You're not actually summing the values - you're declaring a new local variable on each iteration of the loop and doubling an existing value... and what's the array value for? — Jon Skeet
– Jon Skeet, Commented Sep 25, 2013 at 21:37
@JonSkeet Basically what I'm trying to do is create a program that has an array at an unfixed value and finding the average after 5 seconds has been up accordingly to the problem. I'm not quite sure how to initialize a starting value though to continue the run through. The array value was to test how many times after 5 seconds. It has no true meaning, just a test to see. — user2045470
– user2045470, Commented Sep 25, 2013 at 21:42
I don't see where finding the average after 5 seconds comes in. It just has to complete before 5 seconds. Hint: try declaring the total outside the loop, starting with zero, and summing the values. Then think about what an average is... — Jon Skeet
– Jon Skeet, Commented Sep 25, 2013 at 21:44
Difficult to give an answer here - you should take a step back and try to grasp the concepts of arrays and loops before you try to solve this assignment. E.g. you way want to say double[] array = new double[a-lenghth]; to make a same-sized array as "a". — Gyro Gearless
– Gyro Gearless, Commented Sep 25, 2013 at 21:54

luiso1979 · Accepted Answer · 2013-09-25 22:22:08Z

1

If I got it correctly you have to generate an array B where B[i] is the average of the first i elements of the input array.

If this is the problem you can make a single loop that sums A[i] + B[i-1] and then does B[i-1]/i;

So it should be if A is the input array and B is the output:

B[0] = A[0]
for (int i = 1; i < n; i ++) {
    B[i] = A[i] + B[i-1];
    B[i-1] /= i;
}
B[n-1] /= n;

This is O(n) and it is the optimum in terms of complexity (because the problem is of computing the average of n number is T(n), ie it can not be resolved with complexity less than O(n)).

Also the constant is pretty low because you have just a few instructions per loop. This should keep you way bellow the 5 seconds.

Ahh I was forgetting, the generation of A is outside the 5 seconds analysis (it is the input).

Regards

edited Sep 25, 2013 at 22:22

answered Sep 25, 2013 at 21:58

luiso1979

9171 gold badge6 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

luiso1979 Over a year ago

Sorry I just forgot the division of the last element of the array B (the last average). I added it just now

Crickcoder · Accepted Answer · 2013-09-25 21:46:20Z

0

To start make a function to get the average of n given numbers (maxNum)

public int getAvgForNumbers(int maxNum){
int sum = 0;

for(int k=1; k<=maxNum; k++){
     sum = sum + k;
  }

return sum/maxNum;
}

Now use this function to populate your array by calling it starting from value 1 - getAvgForNumbers(1) till a number which you feel will get getAvgForNumbers(x)

answered Sep 25, 2013 at 21:46

Crickcoder

2,1655 gold badges22 silver badges36 bronze badges

Collectives™ on Stack Overflow

Java Array Advice

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related