9
\$\begingroup\$

At a JavaScript test for a job, I was asked the question below. I believe there has to be a better way to accomplish the same result, but I couldn't find any. If some JavaScript geek would take a look and suggest a better approach I would really appreciate it:

Given a positive integer greater or equal to 1, write a function f(n) to calculate as efficiently as possible the sum of the first 1 to n powers of 2. Do no use any buit-in function to calculate the power of a number. Example: if n = 3:

$$ f(3)=2^1+2^2+2^3=2+4+8=14 $$

jsFiddle

function solution (n) {
    var t='';
    var q='';
    for (var i=1;i<=n;i++) {
        q='';
        for (var j=1;j<=i;j++) {
            q=q+'2*';
        }
        q=q+1;
        t=t+'('+q+')+';
    }
    t=t.substr(0,t.length-1);
    return eval(t);
}
\$\endgroup\$
  • 3
    \$\begingroup\$ think of how you'd do it without eval and a bunch of string concatenation. Perhaps with a runningTotal variable and a loop that calculates the next number... Remember, eval is evil - "In JavaScript, the eval() function evaluates a string as code. This involves re-compilation and interpretation of the code at runtime, which is inefficient and is most often not the best design decision." \$\endgroup\$ – Krease Mar 18 '15 at 17:00
  • 1
    \$\begingroup\$ for n>=1, f(n)=(2^(n+1)) - 2 \$\endgroup\$ – Jonathan M Mar 18 '15 at 17:01
  • 2
    \$\begingroup\$ Geometric series : sum(q^k) = (1-q^n)/(1-q)*first_term Here with q=2 that makes f(n)=2^(n+1)-2 \$\endgroup\$ – Cyril DD Mar 18 '15 at 17:12
14
\$\begingroup\$

EVAL, WHY!?

I really can't understand why you're using String concatenation and eval to calculate the result.

The most efficient way is to calculate \$2^{n+1}-2\$.

Additionally, your variable names are all one character long, and your code lacks spacing.

How can you tell what is t and what is q? Your variable names make no sense.

function solution (n) {
    var result = 2;
    for (var i = 1; i <= n; i++) {
        result *= 2;
    }
    return result - 2;
}

Another solution is to use bit shifting: (only works if \$n <= 29\$)

function solution(n) {
    return (2 << n) - 2;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @cybersam, yes because as the documentation says, "The operands of all bitwise operators are converted to signed 32-bit integers in two's complement format." developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… \$\endgroup\$ – Jonathan M Mar 18 '15 at 17:59
  • 1
    \$\begingroup\$ Here's a simple fiddle: jsfiddle.net/63aw8rsk/2 \$\endgroup\$ – Jonathan M Mar 18 '15 at 18:02
  • \$\begingroup\$ Great and sweet, Simon. As per your questions, it is because I am not good enough (yet, hopefully). \$\endgroup\$ – Oriol Vilaseca Mar 19 '15 at 18:10
  • 1
    \$\begingroup\$ Oddly enough, I just discovered that Math.pow() is somehow faster than bit shifting. jsperf.com/division-vs-bit-right-shift/10 . A little mindboggling. Really makes me wonder just what on earth is going on in the internals of Javascript. \$\endgroup\$ – Eric Blade Mar 21 '15 at 21:23
  • \$\begingroup\$ @EricBlade It wouldn't be JavaScript that's funky, it's the interpreter on whatever browser you're using. For what it's worth, in Chrome and Internet Explorer the bitwise rightshift seems faster: jsfiddle.net/zkkwj2k6 \$\endgroup\$ – Thriggle Jul 22 '15 at 20:37
2
\$\begingroup\$

Try the following code:

function power(first, second){
  sum = 1;
  for(var i = 0;i < second;i++){
    sum*=first;
    }
  return sum
  }

function solution(n){
    sum = 0;
    for(var i = 1;i <= n;i++){
        sum+=(power(2, i));
      }
    return sum
    }

alert(solution(2)) //6, 2^1+2^2
alert(solution(3))

First, we define a function to get the power. Second, we declare a variable to keep track of our totals. Then, we loop through each power we want to take (for 3, we want 1, 2, 3, etc.). After, we take the aforementioned power and add it to sum, then proceeding to return that value, all without using eval()!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I was allowed only one function \$\endgroup\$ – Oriol Vilaseca Mar 19 '15 at 18:16
2
\$\begingroup\$

Any time you're dealing with multiplying or dividing by powers of 2, bitwise shifting becomes an option.

x << n is equivalent to x*Math.pow(2,n)

x >> n is equivalent to Math.floor(x/Math.pow(2,n))

Bitwise shifts are extremely efficient, so they're a slam dunk if efficiency is the main concern.

However, if you weren't necessarily dealing with powers of 2, another approach would be called for. Say the next interview question asked you to modify the previous function to work with powers of 3, or to change how \$n\$ affects the calculation... how would you tackle it?

In an interview, this may be your chance to show off that you grasp the concept of recursion. Consider the following solution:

function solution(n) {
    var result = 0; 
    if (n > 0) {
        var sum = 1;
        for(var i = 0; i < n; i++){
            sum = sum*2;
        }
        result += sum + solution(n - 1);
    }
    return result;
}

It works its way down from \$n\$ to 1, adding \$2^n\$ along the way, and returning the sum as a final result.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

In your code, you have nested loops. For small numbers, e.g. n=3, it's not a huge deal, but for large values of n, this could be a problem. The complexity of nested loops is classified in big O notation \$O(n^2)\$.

Then, as others have mentioned, try to avoid eval as much as possible. Especially since the multiplication and accumulation you are doing can be done directly vs building a string and then using eval.

With that said, the other answers show how the problem can be solved with a single loop \$O(n)\$. And the bitwise-shift answer is even better computationally-wise without loops. However see my postscript for why bitwise operations may not work the way you'd expect with JavaScript.

Here's another solution that I came up with without using any loops. It's actually a lot slower than the single loop version provided by Simon Forsberg McFeely, but thought it might be a good example of a "thinking outside-the-box" solution.

//// One liner
function solution(n) {
  return parseInt('1' + new Array(n+2).join('0'), 2) - 2
}

// Same as above but expanded with comments
function solution(n) {
  var ans;

  // Create a new array of length n+2
  ans = new Array(n+2);

  // Join the empty array with 0s
  //  effectively creating a string of 0s with length n+1
  ans = ans.join('0');

  // Append a 1 to the front of the string of zeros
  //  when done, ans contain a string with the 
  //  binary representation of 2^n+1
  ans = '1' + ans;

  // Convert the binary representation string into a decimal number
  ans = parseInt(ans, 2);

  // Finally subtract 2 to get the actual answer
  ans = ans - 2;

  // ... and return the answer 
  return ans;
}

P.S. As mentioned in other answers, binary shifts are very efficient on integers, but that is not necessarily the case in JS. In JavaScript all numbers are actually floating point numbers. When you do a binary shift in JS, the floating point number is implicitly converted to an integer, shifted, then back to floating point again. See here for more. Multiplication on the other hand, is just floating point multiplication.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.