"Utopian Tree" challenge optimization

Question

Problem statement

The Utopian tree goes through 2 cycles of growth every year. The first growth cycle occurs during the monsoon, when it doubles in height. The second growth cycle occurs during the summer, when its height increases by 1 meter. Now, a new Utopian tree sapling is planted at the onset of the monsoon. Its height is 1 meter. Can you find the height of the tree after \$N\$ growth cycles?

Input Format

The first line contains an integer, \$T\$, the number of test cases. \$T\$ lines follow. Each line contains an integer, \$N\$, that denotes the number of cycles for that test case.

Constraints

1 <= T <= 10 
0 <= N <= 60

Sample Input: #01:

2
3
4

Sample Output: #01:

6
7

Explanation: #01:

There are 2 testcases.

N = 3:

• the height of the tree at the end of the 1st cycle = 2
• the height of the tree at the end of the 2nd cycle = 3
• the height of the tree at the end of the 3rd cycle = 6

N = 4:

• the height of the tree at the end of the 4th cycle = 7

My solution:

   'use strict';

function processData(input) {
    var parse_fun = function (s) {
        return parseInt(s, 10);
    };

    var lines = input.split('\n');
    var T = parse_fun(lines.shift());

    var data = lines.splice(0, T).map(parse_fun);
    for (var i = 0; i < data.length; i++) {
        var value = 1;
        for (var j = 0; j < data[i]; j++) {
            if (j % 2 == 0)
                value *= 2;
            else value += 1;
        }
        process.stdout.write(value + '\n');
    }
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) {
    _input += input;
});
process.stdin.on("end", function () {
    processData(_input);
});

The running time is of \$O(n^2)\$. Can anyone tell how to optimize this code to decrease runtime?

Answer 1

A lot of your code seems to be Hackerrank's boilerplate code, so I'll ignore that (though it could use a review), and focus on the "meat" which is:

var value = 1;
for (var j = 0; j < data[i]; j++) {
    if (j % 2 == 0)
        value *= 2;
    else value += 1;
}
process.stdout.write(value + '\n');

(It's run T times of course, but that's irrelevant for now.)

There's not a lot of code there, so there's little to review. Still, the if..else is not great, if you ask me. For one, I'd advice that you always use braces - even for one-liners. But if you don't, at least use linebreaks:

if (j % 2 == 0)
    value *= 2;
else
    value += 1;

However, you can do it all in a ternary, which I would find more appropriate here:

value += (j % 2 === 0 ? value : 1);

The parentheses aren't required, but I find they make it more readable.

Of course, you could also rely on zero being false'y in JavaScript, and just do

value += (j % 2 ? 1 : value);

A slightly faster solution to the even/odd branching would be

value += (j & 1 ? 1 : value);

In other words: If the least-significant bit is 1, the number is odd.

In all, you get:

var value = 1;
for (var j = 0; j < data[i]; j++) {
    value += (j & 1 ? 1 : value);
}
process.stdout.write(value + '\n');

Of course, there may be a purely mathematical, loop-less solution to this. But that's unfortunately not my strong suit.

---

Update: As mjolka points out in the comments, there is a very simple pattern to this. (And I feel pretty dumb for not realizing it.) I can't really explain it more succinctly than mjolka already has, so I'll just quote the comment here:

Look at the first few terms: 1, 2, 3, 6, 7, 14, 15, 30, 31, ... and compare that to powers of two: 2, 4, 8, 16, 32, ...

As is obvious, the output values are all equivalent to a power of 2, minus 1 or minus 2. In code, that can be expressed as a function like so:

// calculate tree height after n cycles
function utopiaTreeHeight(n) {
  var exp = Math.ceil(n / 2) + 1,   // calculate the exponent
      value = Math.pow(2, exp) - 1; // power of 2, minus 1

  return value - (n & 1);           // subtract another 1 if n is odd, and return
}

Which means that the rest of the code is just:

for(var i = 0 ; i < data.length ; i++) {
  var value = utopiaTreeHeight(data[i]);
  process.stdout.write(value + '\n');
}

Now, that's pretty clean, I'd say. Big tip of the hat to mjolka!

Below are my previous (iterative and naïve) solutions. I'll leave them in my answer, only because there's probably something of value in there, even if this particular problem has a much more elegant solution.

(End of update.)

---

Now, about repeating it T times: If you're processing many test cases, it might be worth it to do some pre-processing. All you really need is to iterate to the highest cycle-count. So if you're asked to solve for data = [3, 6, 5] what you really want to just solve for N = 6 but store the intermediate values for N = 3 and N = 5 along the way. You only need to loop once; from zero to N_max.

Of course, doing so will require extra setup, which may be less efficient than simply doing what you're doing now, if there's only one or two test cases.

Just for fun, though, one solution might be:

var cycles = data.length,          // cache this for later
    sorted = data.slice(0).sort(), // copy and sort the input values (slightly faster if you use an explicit comparison function)
    limit  = sorted[cycles - 1],   // get the max
    target = sorted.shift(),       // grab the lowest value (our first target cycle)
    value  = 1,                    // initial tree height
    values = {};                   // a place to store values

// loop to the highest cycle-count (note the range is 0..limit)
for(var n = 0 ; n <= limit ; n++) {
  while( n === target ) {
    // we reached our target cycle, so store the current value
    values[n] = value;

    // and grab the next target
    target = sorted.shift();
  }
  value += (n & 1 ? 1 : value);
}

// print results in the correct order
for(var i = 0 ; i < cycles ; i++) {
  process.stdout.write(values[data[i]] + '\n');
}

The while loop is there to handle duplicates in the input.

A simpler solution would be to simply store every value for N in 0..N_max in an array. That tradeoff would be memory consumption. If data = [1, 923123] you'd end up storing 923121 values (~7MB at worst) you're not going to use. Crazy example, but if you don't know your input, well...

Still, such an approach could look like:

var limit = Math.max.apply(null, data),
    values = [],
    value = 1;

for(var n = 0 ; n <= limit ; n++) {
  values.push(value);
  value += (n & 1 ? 1 : value);
}

for(var i = 0 ; i < data.length ; i++) {
  process.stdout.write(values[data[i]] + '\n');
}

Answer 2

I know it's a jscript code review, but since you're chasing efficiency it's all about algorithm/formula (rather than language), so here's how to eliminate all the looping (i.e. calculate in O(1)). Try it first in Excel (INT() is traditional TRUNC()/FLOOR() and MOD(a,b) is remainder after a / b (so we're working only with integers).

N is season number, h the height (at the end of that season)

h = (2^(INT(N/2)+1)-1)*(1+INT(MOD(N,2)))

In C#

  for (int n = 0; n < 10; n++)
  {
    Console.WriteLine($"{n,2}, {(Math.Pow(2, n / 2 + 1) - 1) * (1 + n % 2),3}");
  }

Output

 0,   1
 1,   2
 2,   3
 3,   6
 4,   7
 5,  14
 6,  15
 7,  30
 8,  31
 9,  62

Answer 3

Use preprocessed values.

function processData(input) {
    var parse_fun = function (s) {
            return parseInt(s, 10);
        },
        heights = function() {
            var result = [1]
            for (var i = 1; i <= 60; i++) {
                if (i & 1) {
                    result[i] = result[i-1] * 2;
                } else {
                    result[i] = result[i-1] + 1;
                }
            }
            return result;
        }();

    var lines = input.split('\n');
    var T = parse_fun(lines.shift());

    var data = lines.splice(0, T).map(parse_fun);
    for (var i = 0; i < data.length; i++) {
        process.stdout.write(heights[data[i]] + '\n');
    }
}

In this case complexity is \$O(n+t)\$