Optimized solution to calculate first powers of 2

I experienced many programming contests and olympiads but this one was really different. In a programming contest on Hacker Rank, I faced with a challenging problem and it was the main reason I failed the test. That question made me nervous and stressful so I gave up. When I found the solution after the test, I laughed so loud.

The question is:

Calculate sum of first powers of 2 without using any built-in language API to calculate the power. Implement optimized solution.

Well, there are two factors. First, not using built-in functions like Math.pow and second implementing the optimized solution. So, of course a recursive function or for-loop is not the answer.

 Answer

Use bitwise operations. How? Ok, let me show you a trick.

parseInt(10, '2')    == Math.pow(2, 1); //2^1 = 2
parseInt(100, '2')   == Math.pow(2, 2); //2^2 = 4
parseInt(1000, '2')  == Math.pow(2, 3); //2^3 = 8
parseInt(10000, '2') == Math.pow(2, 4); //2^4 = 16
//and so on

So, how to make 10, 100 or 1000? Using shift operations you can make it:

1 << 1 //2
1 << 2 //4
1 << 3 //8
1 << 4 //16

A short explanation of above source code is that the binary of 1 is 00000001 and when you use left shift operator, the result is 00000010, 00000100 and so on.

So the answer is to use a for-loop for N:

var sum = 0;
for (var i = 1;i <= n;i++) {
  sum += 1 << i;
}
console.log(sum);

 Can we make it better?

Yes. Here is the final hack.

The sum of first N powers of 2 is 2^(N + 1) - 2. For instance, n = 3:

(2 ^ (3 + 1)) - 2 = 16 - 2 = 2 + 4 + 8 = 14

And then, using bitwise operations we have:

console.log((2 << n) - 2);

Please note that the binary of 2 is 00000010.

Actually, this is the right answer.

Edit: You can find more interesting examples here: http://www.cs.utsa.edu/~wagner/knuth/fasc1a.pdf

Source: New feed

Leave a Reply

Your email address will not be published. Required fields are marked *