diff options
| -rw-r--r-- | challenge-079/abigail/node/ch-1.js | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/challenge-079/abigail/node/ch-1.js b/challenge-079/abigail/node/ch-1.js new file mode 100644 index 0000000000..6c9ca09ace --- /dev/null +++ b/challenge-079/abigail/node/ch-1.js @@ -0,0 +1,53 @@ +// +// Challenge: +// +// You are given a positive number $N. +// +// Write a script to count the total numbrer of set bits of the binary +// representations of all numbers from 1 to $N and return +// $total_count_set_bit % 1000000007. +// +// https://perlweeklychallenge.org/blog/perl-weekly-challenge-079/ +// + +// +// This is A000778 (https://oeis.org/A000788). There's a recursive formala +// for the number of bits in the binary representation of 0 .. $N: +// +// bits (0) = 0 +// bits (2 * N) = bits (N) + bits (N - 1) + N +// bits (2 * N + 1) = 2 * bits (N) + N + 1 +// + +// +// Create an interface to read from STDIN +// +const rl = require ('readline') . createInterface ({ + input: process . stdin, +}); + +// +// Read lines of input, calculate the result, and print it. +// +rl . on ('line', (line) => { + console . log (bits (+line)); // Unary + numifies +}); + + +// +// Recursive function to calculate the results (see above). +// +let cache = []; +function bits (n) { + if (n == 0) { + return 0; + } + + if (!cache [n]) { + let half = Math . floor (n / 2); + cache [n] = bits (half) + half + + (n % 2 ? bits (half) + 1 : bits (half - 1)); + } + return cache [n]; +} + |