I just got this challenge and I got stumped, blank. The question somewhat goes like this:

There are chess players that will play in duels. For example, 4 players (A, B, C, D), paired by 2, will yield a total of 6 chess games: AB, AC, AD, BC, BD, CD. Write a function taking an integer value and returning the number of possible combination.

Tests:

gameCount(4);     // 6
gameCount(10000); // 49995000

I remember, many years ago, my math class on linear problems, and this was one of them. A very quick Google search yielded the nCr formula. So I quickly wrote the code:

const r = 2;
const factorial = n => {
  let f = 1;
  for (let i = 2; i <= n;   i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n) / (factorial(r) * factorial(n - r));

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // NaN

The NaN baffled me at first, but then I realized that 10000! is quite a large number!

How can I optimise gameCount to accept large numbers by still remaining linear?

Note: I am aware that the factorial function is not linear, but this was what I wrote at the time. The ideal solution would be to have everything linear, perhaps removing factorials altogether.

CodePudding user response：

What you currently do is calculate two very big numbers that share a very big common divisor, and then divide one by the other. You could just not calculate that divisor (factorial(n - r)) in the first place.

Change your factorial function to take a minimum argument.

const r = 2;
const factorial = (n, m) => {
  let f = 1;
  for (let i = n; i > m; --i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n, n - r) / factorial(r, 0);

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // 49995000

Though note that this will only avoid the NaN issue as long as r is reasonably small. If you need it to work for cases where both n and r are big, you cannot use the native JavaScript number type. I suggest looking into BigInt for that case.

And for the sake of completeness, if the case r = 2 is all you care about, then your entire formula can be simplified to:

const gameCount = n => (n * (n - 1)) / 2;