This problem is a prime example of the creative genius at work at leetcode where you’re given a problem that on the surface appears to intuitive to solve, and yet the further you dig into it, the more it rears its ugly head.

I want to start off by saying I actually solved this one up to the last test case using naive recursion, which IMO is the intuitive solution. It works great until you encounter a problem in which the numbers are so large you end up blowing the heap. The solution I developed for that is as follows:

I’m not really going to walk through this for two reasons:

It doesn’t pass the last test case

It’s the result of an hour of being driven mad by this problem and it this point I don’t even know what it’s doing either (aside from being a recursive solution that almost works but blows the heap with large input).

At this point I think what probably should happen is that a tail recursive solution is developed to stop the stack from overflowing. Unfortunately, I found by applying an incredibly check, I can actually solve this problem using my original algorithm :)

Specifically, look to lines 13-15 to see my “clever” addition that beat the system. Obviously, this is would be a pretty sad solution for a mission critical production program. However, for being the daily challenge, I’m going to take it!