Average of Prefix

Summary

Given an array of integers, calculate the average of all prefixes (subarrays ending at each index). This problem involves arrays and mathematical concepts.

Detailed Explanation

To solve this problem, we can use a prefix sum approach. A prefix sum is the cumulative sum of elements up to a certain point in the array. We'll keep track of the running sum as we iterate through the array, and then calculate the average by dividing the current sum by the index plus one.

Here's the step-by-step breakdown:

1. Initialize an empty array prefixSums to store the prefix sums.
2. Iterate through the input array arr. For each element at index i, add the current element to the running sum and append it to prefixSums.
3. To calculate the average of a prefix, simply divide the corresponding prefix sum by (i + 1).
4. Return the calculated averages as an array.

Here's an ASCII art diagram illustrating the process:

arr = [1, 2, 3, 4, 5]
prefixSums = []
runningSum = 0

for i in range(len(arr)):
    runningSum += arr[i]
    prefixSums.append(runningSum)

averages = []
for i in range(len(prefixSums)):
    averages.append(prefixSums[i] / (i + 1))

print(averages)  # Output: [1.0, 1.5, 2.0, 2.5, 3.0]

The time complexity of this solution is O(n), where n is the length of the input array. The space complexity is also O(n) due to the prefixSums array.

Optimized Solutions

Java