javascript – Solve binomial coefficient without lookup

A review of the first 5 lines

Only looking at the code related to the problem and ignoring the testing code as it looks haphazardly put together.

Thus

const MAX_BASES = 10;
const range = n => new Array(MAX_BASES).fill(0);
const binomialCoefficient = n => (Math.pow(n, 2) + n) / 2;
const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i));
const toBase = n => baseMax.indexOf((...baseMax).reverse().find(max => n > max)) + 1;

Minor point

You should use the operator ** (Exponentiation) rather than the math function Math.pow . Both ** and Math.pow use the same pow function under the hood so there is no performance difference, however ** is cleaner.

The bad part

The only thing that is bad in your code, even assuming you are forced to lookup the values, is that every time you call toBase you recreate the array, reverse it, and then search it.

To get the correct value subtract the index from the arrays length. There is an edge case when the input is 0. That can be handled with a ternary.

You only need to reverse the array once.

 const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i)).reverse();

Subtract the index from the arrays length to get the result you are after. The edge case n = 0 can be handled with a ternary.

 const toBase = n => !n ? 0 : baseMax.length - baseMax.indexOf(baseMax.find(max => n > max));

Rather than use Array.find you can use Array.findIndex This will save you having to search the array twice, once to find the value n <= max then again to find the index with Array.indexOf

Thus you get

 const toBase = n => !n ? 0 : baseMax.length - baseMax.findIndex(max => n > max);

And you don’t need to reverse the array which makes it even simpler

 const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i));
 const toBase = n => !n ? 0 : baseMax.findIndex(max => n <= max);

A functional solution.

The function (n ** 2 + n) / 2 is a quadratic $frac{1}2n^2 + frac{1}2n + 0 = y$

You can solve the quadratic when $y=0$ using $begin{array}{*{20}c} {x = frac{{ – b pm sqrt {b^2 – 4ac} }}{{2a}}} \ end{array}$

However as we change $n$ the solution we are after is no longer at $y = 0$

If we move the parabola down so that $y$ is at 0 for the value $n$ we are solving for we can then solve for any value of $n$

The quadratic to solve is $frac{1}2x^2 + frac{1}2x – n = 0$

$ {x=frac{{-frac{1}2+sqrt{frac{1}4-4*frac{1}2*-n} }}{{2*frac{1}2}}}$

which is

$x=-frac{1}2+sqrt{frac{1}4+2n} $

Now we get $x$ for $n$ and round it up when $x$ is a fraction.

The rewrite

An thus the 5 lines become one line.

const toBase = n => Math.ceil(-0.5 + (0.25 + 2 * n) ** 0.5);