RabbitFarm

Part 1

You are given a positive number $N. Write a script to count the total number of set bits of the binary representations of all numbers from 1 to $N and return $total_count_set_bit % 1000000007.

Solution

Sample Run

$ perl perl/ch-1.pl
5 % 1000000007 = 5
4 % 1000000007 = 4

Notes

The approach here is to continuously shift bits off to the right, checking to see if the bit about to be shifted off is set or not. This is a pretty standard pattern and it looks pretty much the same in C++ and Prolog too!

Part 2

You are given an array of positive numbers @N. Write a script to represent it as Histogram Chart and find out how much water it can trap.

Sample Run

Notes

This is one of the more fun sorts of problems that come up in these challenges! It is somewhat similar to the “leader problem” from last week in that we are given an array of numbers and need to do a similar set of look ahead comparisons. Here we look ahead in the array to determine if what I call buckets exist. Whatever buckets are found are then used to compute the total volume as specified.

References

https://users.cs.cf.ac.uk/Dave.Marshall/PERL/node36.html