4 ms·
The Britney Spears Problem
- Sam_Odio 18y ago> ... calculating the average (or arithmetic mean) of a stream's integers takes three registers and three operations per integer. One register counts the elements, another records their sum, and the third register holds the value of the average, calculated as the quotient of the sum and the count. Here's an easy brain teaser: do the above using only two registers.
- ajkirwin 18y agoYou could.. multiply the average register by the count register, then add the new integer to the average register, increment the count register and then re-divide?
- ramchip 18y agoHow about a special running average: keep the count in one register and the average in the other one. Let's say N is the current count and av the average. The algorithm is in C-style notation: void addElement( int val ) { ++N; av = ((N - 1) * av / N) + val / N; } I have used a similar trick (with a fixed N) to implement a cheap running average for an image acquisition software and it works quite well, but of course if N is very large val / N becomes negligible.
- hack_edu 18y agoYou guys are so goddamn geeky! <3
- 3ijsflksflk 18y agoconstant space ftw
- Boxer 18y agoLet average-so-far=a, count=c. When you add a new item x, the new average is: a = a + (x-a)/(c+1)
- jlhamilton 18y agoI posted this a while back, but it didn't get many votes. http://news.ycombinator.com/item?id=243270 http://news.ycombinator.com/item?id=243270