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.