Dynamic programming: Code Wars: twice linear: algorithm times out

Question

I am struggling with a Kata in Code Wars: https://www.codewars.com/kata/5672682212c8ecf83e000050/train/javascript
The idea is to create a sequence of numbers, where each number is created reclusively following this two formulas:

y=2x + 1  
z=3x + 1  

With x being the current number in the sequence.

Starting with 1, the sequence would grow like this:

sequence = [1]  
x = 1  
y = 2*1 +1 = 3  
z = 3*1 + 1 = 4  
leading to sequence = [1, 3, 4]

Applying it to the next numbers leads to:

x = 3  
y = 2*3 + 1 = 7  
z = 3*3 + 1 = 10  
leading to sequence = [1, 3, 4, 7, 10]  

x = 4  
y = 2*4 + 1 = 9  
z = 3*4 + 1 = 13  
sequence [1, 3, 4, 7, 9, 10, 13]  

And so forth. Notice that I sorted the sequence in the last step, as the results of x=4 (9 and 13) have to be mixed with the results of x=3 (7 and 10) to keep an ordered sequence.

[1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

I was able to solve the problem correctly, but the implementation is supposed to be efficient and I am timing out. My code:

function dblLinear(n) {
  cache = {};
  cache[0] = 1;
  res = [1];
  lengthCounter = 0
  if (n === 0) {
    return 1;
  }
  for (var i = 1; i < n + 10; i++) {
    //console.log("i ", i)
    if (cache[i] === undefined && res.includes(i)) {
      //console.log('i: ', i, ' el1: ', i * 2 + 1, ' el2: ', i * 3 + 1);
      cache[i] = [i * 2 + 1, i * 3 + 1]
      if (!res.includes(i * 2 + 1)) {
        res.push(i * 2 + 1);
      }
      if (!res.includes(i * 3 + 1)) {
        res.push(i * 3 + 1);
      }
      //console.log("res ", res)
    }
    if (res.length !== lengthCounter) {
      var arrStart = res.slice(0, Math.floor(res.length / 2));
      var arrEnd = res.slice(Math.floor(res.length / 2), res.length)
      arrEnd.sort(function(a, b) {
        return a - b;
      });
      res = arrStart.concat(arrEnd)
      lengthCounter = res.length
    }
  }
  //console.log('res ', res);
  return res[n];
}

As you can see in my code, I tried some simple tricks to increase the efficiency but I 'm guessing I need more speed gains. What do you think is the problem and how could I increase the efficiency?

Any help will be greatly appreciated!

Cheers

Manuel

Answer 1

This problem can be solved in O(n). The idea is to keep track which element was generated last and add the smaller one of the two possibilities, so the elements are added in order. This code passes all the tests easily.

function dblLinear(n) {
    let u = [1], x = 0, y = 0
    for (let i = 0; i < n; i++) {
        let nextX = 2 * u[x] + 1, nextY = 3 * u[y] + 1
        if (nextX <= nextY) {
            u.push(nextX)
            x++
            if (nextX == nextY)
                y++
        } else {
            u.push(nextY)
            y++
        }
    }
    return u[n]
}

console.log(dblLinear(10) + " = " + 22)
console.log(dblLinear(20) + " = " + 57)
console.log(dblLinear(30) + " = " + 91)
console.log(dblLinear(50) + " = " + 175)
console.log(dblLinear(100) + " = " + 447)

Answer 2

The good solution for this

function dblLinear(n) {
  var ai = 0, bi = 0, eq = 0;
  var sequence = [1];
  while (ai + bi < n + eq) {
    var y = 2 * sequence[ai] + 1;
    var z = 3 * sequence[bi] + 1;
    if (y < z) { sequence.push(y); ai++; }
    else if (y > z) { sequence.push(z); bi++; }
    else { sequence.push(y); ai++; bi++; eq++; }
  }
  return sequence.pop();
}

console.log(dblLinear(10) + " = " + 22)
console.log(dblLinear(20) + " = " + 57)
console.log(dblLinear(30) + " = " + 91)
console.log(dblLinear(50) + " = " + 175)
console.log(dblLinear(100) + " = " + 447)

Answer 3

The existing solution is great but my solution to this problem is

function dblLinear(n) {
  let eq1Index = 0;
  let eq2Index = 0;
  let eq1Array = [3];
  let eq2Array = [4];
  let result = 1;
  for (let i = 1; i <= n; i++) {
    if (eq1Array[eq1Index] < eq2Array[eq2Index]) {
      result = eq1Array[eq1Index];
      eq1Index++;
    } else {
      result = eq2Array[eq2Index];
      eq2Index++;
    }

    eq2Array.indexOf(2 * result + 1) == -1 && eq1Array.push(2 * result + 1);

    eq2Array.push(3 * result + 1);
  }
  return result;
}
console.log(dblLinear(10) + " = " + 22)
console.log(dblLinear(20) + " = " + 57)
console.log(dblLinear(30) + " = " + 91)
console.log(dblLinear(50) + " = " + 175)
console.log(dblLinear(100) + " = " + 447)