MockVita Dole Out Cadbury - MLE

I get Memory Limit Exceeded for the DP solution to the Dole Out Cadbury problem in MockVita 2.
The problem statement and my solution are both in this link: Online Compiler and IDE - GeeksforGeeks

The idea is that two rectangles of the same proportion give out the same number of asked squares, so I every time I need the squares for a rectangle of a particular proportion - I look for it in the dictionary, if not found I will calculate and store it for later access.

Classic DP solution, yet it gives Memory Limit Exceeded.

Please point out the whether the flaw is in program logic or the Dp approach.

Thank you.

Maybe the flaw is you are dp[], try to solve it in O(1) space complexity.
The constraints of this question are not big, you can increase the time complexity of your program to reduce space.

I also faced the same issue, but was resolved when i submitted the solution with constant space complexity.

Yes , because you need to solve it by brute forcing all possible values…without using any vector or matrix i guess :slight_smile:

I don’t think it is a DP problem. I have solved it using gcd (subtraction method).