Nasty overflow problem


The problem itself isn’t too difficult (just calculating n’th Catalan number),
but after all it boils down to a nasty overflow problem with weird test cases created by Interviewbit.

It’s really annoying because if A is large, it will create an overflow anyway. And any result that exceeds long long int needs a big arithmetic support from a library in practical settings. We would rather want to have an exact number in practical software application instead of finding a modulo with an arbitrary number 1e9+7. If there isn’t a constraint with a nasty modulo with 1e9+7, there is an O(n) algorithm that exploits the recurrence equation, instead of having an O(n^2) with dp. I think this problem was pretty much a big waste of time IMO.

With Python which comes with a built-in big arithmetic support, I could come up with an O(n) solution with no problem, though. I’d rather recommend solving this problem with Python instead of C++ if you have to.