Here's the thing, I have a task to make an array with some numbers, after that the array can accept any other numbers of the the same type inside on any position. When I get the final array (with the added numbers) I need to find the average of the numbers inside with a constant O(1) time. How do I do that?! Here's what I have as an example
Elements: 5 12 7 9 31 Average: 12.8
If this is an array class you can keep track of the sum of all of the numbers as they are added and updated. Then when all updates are complete just divide the sum by the number of elements to get the average, and just the calculation of the average will be O(1) since the sum was precomputed.
If this is a raw memory array that you are simply passed, then calculating the average will require summing all of the number, which is an O(N) unless someone is playing a semantics game regarding what an operation is.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With