HackerRank Week Of Code 23

Stirling numbers are coefficients of polynomial, which is product of n linear polynomials, right? So, we can start with n linear polynomials, multiply two of them each step and end up with one polynomial of degree n? Multiplication of the polynomials could be done via Karatsuba in pow(n, 1.5) (approximately), right? It gives us asymptotic better than n².

Div conquer adds log(n) to the above, so pow(n, 1.5)*log(n) is hard to get under time limit. On the other hand, FFT which is n*log²(n) is annoying to get right under mods.

--

--

Creator of https://github.com/servicetitan/Stl.Fusion , ex-CTO @ ServiceTitan.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store