I've been trying to solve this kata on codewars. I've got an algorithm, but it's apparently too slow to pass the test. It can create sequence of 2450 numbers in just under 1.6 seconds. I don't need the solution but the hint or something to help me to make my algorithm faster.

function ulamSequence(u0, u1, n) {
  // create an array with first two elements in it
  const seq = [u0, u1];
  
  // create a loop that checks if next number is valid and if it is, push it in seq
  num: for (let i = u1   1; seq.length < n; i  ) {
    let sumCount = 0;
    for (let k = 0; k < seq.length - 1; k  ) {
      if (seq.indexOf(i - seq[k]) > k &&   sumCount === 2) { continue num; }
    }
    sumCount === 1 ? seq.push(i) : "";
  }
  
  return seq;
}

CodePudding user response：

Here's an idea: have an array sums so that sums[N] keeps the number of possible summations for N. For example, for U(1,2) sums[3] will be 1 and sums[5] will be 2 (1 4, 2 3). On each step, locate the minimal N so that N > last item and sums[N] == 1. Add N to the result, then sum it with all previous items and update sums accordingly.

function ulam(u0, u1, len) {
    let seq = [u0, u1]
    let sums = []
    let last = u1

    sums[u0   u1] = 1

    while (seq.length < len) {
        last  = 1
        while (sums[last] !== 1) {
            last  = 1
        }
        for (let n of seq) {
            let s = n   last
            sums[s] = (sums[s] || 0)   1
        }
        seq.push(last)
    }
    return seq
}

console.time()
ulam(1, 2, 2450)
console.timeEnd()

CodePudding user response：

function ulamSequence(u0, u1, n) {
  const seq = [u0, u1];
  const set = new Set(seq);

  for (let i = u1   2; seq.length < n; i  ) {
    let sumCount = 0;
    for (let k = 0; k < seq.length - 1; k  ) {
      if (set.has(i - seq[k])) {
        sumCount  ;
        if (sumCount === 2) {
          continue;
        }
      }
    }
    if (sumCount === 1) {
      seq.push(i);
      set.add(i);
    }
  }
  return seq;
}