3
\$\begingroup\$

I've written a JavaScript function that generates a row of consecutive odd numbers in a triangle. The triangle looks like this:

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29

The function takes a row index (1-indexed) and returns the corresponding row.

For example:

oddRow(1)  ==  [1]
oddRow(2)  ==  [3, 5]
oddRow(3)  ==  [7, 9, 11]

Here's the code I've written:

function oddRow(n) {
  let res = [];
  let last = 1;
  for (let i = 1; i < n + 1; i++) {
    let arr = [];
    for (let j = 0; j < i; j++) {
      arr.push(last);
      last += 2;
    }
    res.push(arr);
  }
  return res[res.length - 1];
}

My code works well for small row indices, but it fails to run for large indices like 154716. I'm looking for ways to optimize my code so that it can handle large row indices.

I'm particularly interested in approaches that might leverage patterns or mathematical properties of this triangle of consecutive odd numbers to improve the function's efficiency.

Any help or suggestions would be greatly appreciated.

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Quadratic, Linear, or Constant

This is a linear problem \$O(n)\$ (possibly constant \$O(1)\$ See bottom of answer) however your solution is quadratic \$O(n^2)\$.

Note: that the function expects that the machine has the memory needed to store up to Number.MAX_VALUE rows (Very big number). This is far from what is possible, as the floating point number system will break well before you get close to that many rows (even if you had the multi-universe spanning memory store)

You should set an upper limit to the number of row your function will calculate.

Store only the last row.

You need to dump the previous calculated rows of data using your current method.

As it is only the last row you want that should be the only row that gets stored. Example still quadratic

function oddRow(n) {
    const res = [];
    var value = 1, i = 0, j;
    while (i < n) {
        j = 0;
        while (j < i) {
            j ++;
            value += 2;
        }
        i++;
    }
    j = 0;
    while (j < i) {
        res.push(value);
        j ++;
        value += 2;
    }
    return res;
}
console.log(oddRow(5).join(",")); // should be "21,23,25,27,29"

Adding values, no multiply

The inner loop is adding 2 to a value i times. That is the same as adding 2 * i. We can remove the inner loop completely.

Example is now quasilinear (my guess)

function oddRow(n) {
    const res = [];
    var value = 1, i = 0, j = 0;
    while (i < n) {
        value += i * 2;
        i++;
    }
    while (j < i) {
        res.push(value);
        j ++;
        value += 2;
    }
    return res;
}
console.log(oddRow(5).join(",")); // should be "21,23,25,27,29"

Area of a triangle

Do we really need to calculate the start of each row. All the rows represent a triangle with the end value sitting on top of the diagonal line. We add half of the count of end values to the area of the triangle

The number of numbers in a number triangle of height n is (n + 1) * n / 2

The number of values on the last row is n.

Thus the first value of row n is n * (n - 1) / 2 * 2 + 1 which simplifies to n * (n - 1) + 1

Now we can calculate the first value of the row we want and fill the array with n odd values from that value.

Reducing your quadratic \$O(n^2)\$ solution to a linear \$O(n)\$ in both storage and complexity.

function oddRow(n) {
    const res = [];
    var value = (n - 1) * n + 1;
    const nextRow = value + 2 * n;
    while (value < nextRow) {
        res.push(value);
        value += 2;
    }
    return res;
}
console.log(oddRow(1).join(",")); // should be "1"
console.log(oddRow(2).join(",")); // should be "3,5"
console.log(oddRow(3).join(",")); // should be "7,9,11"
console.log(oddRow(4).join(",")); // should be "13,15,17,19"
console.log(oddRow(5).join(",")); // should be "21,23,25,27,29"

Constant solution \$O(1)\$ ??

There is a solution that returns a function that will return the nth value on the nth row. Meaning you need only calculate the starting value of the nth row and the number of values in the row n.

If you only need the 1 - millionth value of the 2 - billionth row this is by far the best solution.

This solution is constant \$O(1)\$ however the burden of complexity is passed on to the user of the data.

I will leave that up to you if you wish to try.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much! You are an incredible developer, and I truly appreciate your amazing explanations and clear, efficient code. I am deeply grateful. \$\endgroup\$
    – XMehdi01
    Commented May 7 at 16:37
3
\$\begingroup\$

memory consumption

it fails to run for large indices

I'm guessing due to malloc() fail.

The OP computes (roughly) a 2-dimensional matrix:

      arr.push(last);
      ...    
    res.push(arr);
  }

Yet we're returning just a 1-D vector.

  return res[res.length - 1];

There's no reason to retain (the lower-left triangle of) that whole giant matrix. The quadratic space complexity won't make you happy.

If we were computing binomial coefficients I would counsel retaining just the previous row.

But here, there's no need to even store values until we arrive at the desired row.

math

approaches that might leverage patterns or mathematical properties of this triangle

Let's focus on initial value in each row. We'll take a look at consecutive differences.

   1   3   7  13  21
     2   4   6   8

So e.g. 21 - 13 == 8, and so on.

Alas, those integers don't really suggest google search terms to you. So I will offer a few candidates. Let's see, "arithmetic sequence"? Hmmm, might be promising, but does it fit? Or its bigger cousin, "geometric sequence"? Wikipedia can even tell you about triangular numbers.

See if you can find an expression which predicts initial value of the hundredth or the thousandth row, without computing any intermediate row values.

With that in hand, can you solve the sub-problem of producing the row values which follow that initial value? Please post a new answer; I will upvote it.

\$\endgroup\$

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.