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
  • 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, 2015 at 17:00
  • 1
    \$\begingroup\$ for n>=1, f(n)=(2^(n+1)) - 2 \$\endgroup\$
    – Jonathan M
    Mar 18, 2015 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, 2015 at 17:12

4 Answers 4

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;
}
\$\endgroup\$
5
  • \$\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, 2015 at 17:59
  • 1
    \$\begingroup\$ Here's a simple fiddle: jsfiddle.net/63aw8rsk/2 \$\endgroup\$
    – Jonathan M
    Mar 18, 2015 at 18:02
  • \$\begingroup\$ Great and sweet, Simon. As per your questions, it is because I am not good enough (yet, hopefully). \$\endgroup\$
    – Grumoll
    Mar 19, 2015 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, 2015 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, 2015 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()!

\$\endgroup\$
1
  • \$\begingroup\$ I was allowed only one function \$\endgroup\$
    – Grumoll
    Mar 19, 2015 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.

\$\endgroup\$
0
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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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