100th percentile. Perfection.

Honestly, this solution took me a while to wrap my head around. The reformulated problem statement so faintly resembled the original one that I had trouble convincing myself of the correctness of the solution (i.e. that solving the reformulated problem solves the original one). I found that the best way to truly understand the solution is to step through it line-by-line, and really understanding what each step does.

This article has been a blast to write, and I think it's amazing how we were able to bring our runtime down from 377ms to 1ms by optimizing our solution. Even just simply caching our solutions (through memoization) reduced our runtime to 8ms, which is an extremely significant improvement.

I hope you had as much fun digesting these solutions as I did writing them!