DEV Community

hk7math
hk7math

Posted on • Edited on

JavaScript Big Combination Problem

#javascript #mathematics #es6 #todayilearned

A recent CodeSignal Challenge was to calculate 1000C500 (mod 1e9+7) and I got defeated =(

All my trials exceeded the time limit.. Here is the best JS solution by psr
, could anyone explain what happens in this line??? I learnt ES6 but got no idea about this syntax...

f[o = n + 1/k] = o in f
Enter fullscreen mode Exit fullscreen mode

full solution for reference, please tell me to delete this if I violated any rule...

f = countWays = (n, k) => f[o = n + 1/k] = o in f ? f[o] : k ? n && (f(--n, k) + f(n, k - 1)) % (1e9 + 7) : 1
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
hk7math profile image
hk7math • • Edited

Thanks Barbar's comments in StackOverflow, I understand the algorithm now.

The algorithm can be rewritten as follows:

f = nCk = (n, k) => { //Declare both f and nCk as the same function let o = n + 1/k //o will be the key of function object f f[o] = o in f //Define f[o] based on a nested ternary expression ? f[o] //Avoid recalculation if f has key o already  : k==0 //nC0 is always 1 ? 1 : n<k //nCk is improper and assigned 0 if n<k ? 0 : f(--n, k) //Do recursion nCk = (n-1)Ck + (n-1)C(k-1) + f(n, k - 1) return f[o] //Done! }
Enter fullscreen mode Exit fullscreen mode

Here goes an example of 5C2

f(n,k) n k o f[o] f(5,2) 5 2 5.5 f[5.5]=f(4,2)+f(4,1)=10 f(4,2) 4 2 4.5 f[4.5]=f(3,2)+f(3,1)=6 f(3,2) 3 2 3.5 f[3.5]=f(2,2)+f(2,1)=3 f(2,2) 2 2 2.5 f[2.5]=f(1,2)+f(1,1)=1 f(1,2) 1 2 1.5 f[1.5]=f(0,2)+f(0,1)=0 f(0,2) 0 2 0.5 f[0.5]=0 f(0,1) 0 1 1 f[1]=0 f(1,1) 1 1 2 f[2]=f(0,1)+f(0,0)=1 f(0,0) 0 0 Inf f[Inf]=1 //Inf aka Infinity f(2,1) 2 1 3 f[3]=f(1,1)+f(1,0)=2 f(1,0) 1 0 Inf f[Inf]=1 f(3,1) 3 1 4 f[4]=f(2,1)+f(2,0)=3 f(n,0) n 0 Inf f[Inf]=1 f(4,1) 4 1 5 f[5]=f(3,1)+f(3,0)=4
Enter fullscreen mode Exit fullscreen mode

P.S. I got a few takeaways when investigating into this algorithm

  1. Double declaration of function on the same line as a trick for recursion

  2. Immediate use of a key with its value just assigned

  3. Infinity can be used as a key of an object(!)

  4. Syntax o in f checks if object f has the key o