I used memoization to solve the problem: Solution: 64796703 | CodeChef however I get WA for some reason.

Here’s an AC solution: Solution: 64549289 | CodeChef

The problem constraint says that N would lie between an inclusive range of 1 and 10^5.

I compared the AC solution and my DP solution for each N where 1<=N<=10^5, here’s the jdoddle: Online Compiler and Editor/IDE for Java, C/C++, PHP, Python, Perl, etc. `solve1`

is my solution. `solve2`

is the AC O(1) solution. All the answers for each N are equal for both solutions. Not sure what test case fails.