i solved a problem featured on the yc company interviewstreet.com codesprint.<p>the problem: Count the number of one-bits from 0 to 2^n - 1, for n from 1 to 20.<p>my solution: <a href="http://i.imgur.com/hUxt0.png" rel="nofollow">http://i.imgur.com/hUxt0.png</a><p>when you run the solution:<p><pre><code> Number of one-bits in 1 bit numbers from 0 to 1 = 1
Number of one-bits in 2 bit numbers from 0 to 3 = 4
Number of one-bits in 3 bit numbers from 0 to 7 = 12
Number of one-bits in 4 bit numbers from 0 to 15 = 32
Number of one-bits in 5 bit numbers from 0 to 31 = 80
Number of one-bits in 6 bit numbers from 0 to 63 = 192
Number of one-bits in 7 bit numbers from 0 to 127 = 448
....</code></pre>
JS:<p><pre><code> var list;
var x;
var prev;
var onebits;
var doubleatprev;
list = [];
list[0] = 1;
list[1] = 4;
for (x = 2; x <= 20; x++) {
prev = x;
onebits = Math.pow(2, prev);
doubleatprev = list[x - 1] * 2;
list[1 + x - 1] = onebits + doubleatprev;
}
for (x = 1; x <= 20; x++) {
window.alert(['Number of one-bits in ',x,' bit numbers from 0 to ',Math.pow(2, x) - 1,' = ',list[x - 1]].join(''));
}
</code></pre>
Took 15 minutes to code up and 45 minutes to debug the array indexing :) One of these days I'll be able to write the JS and get the Blockly instead of the other way around - that'd be super awesome!