I know what the error is, but how to resolve it

#1

the code cannot handle 1000 000 000 case, because it throws an runtime error with out of memory exception. how to handle this case?

#2

@mudit2jain
every dynamic problem,can be solved by using both bottom up(Tabulation) and top down(Memoization) manner.
Please try to write your code in top down Method(Memoization) using HashMap,
as unlike Array,HashMap uses only the required space.

#3

I tried with hashmap but it is giving timelimit for both the test cases

#4

@mudit2jain
It will give TLE,as constraint is quite large n is nearly 10^9.
Please use recursive storage DP method also known as Memoization.

#5

The code works by using hashmap in recursive storage but i dont understand why it works in recursive one and not in iterative one. Whats the difference. In recursive one we also have to check the hashmap for every recursive call and for iterative we also need to check hashmap for all three parameters.
Can you please tell me the underlying concept behind this?

#6

Yes,the major difference in time complexity lies between the two.

First one,i.e.the Tabulation method(iterative storage)is having Time Complexity of O(n),as the for loop completely iterates over n.
We dont have any control to stop this for loop to iterate over complete n.

for(int i = 2; i <= n; i++) {
int temp = map.get(i/2) + map.get(i/3) + map.get(i/4);
map.put(i, Math.max(temp,i));
}

Second one,i.e. the Memoization method(recursive storage) only use recursive calls when it didn’t find the one searching for in HashMap,hence having a logarithmic time complexity,log(n).

1 Like