Exchanging Coins Problem

#1

One testcase is Showing Run Time Error. Please help me to find the mistake.
The link to the sol is :-

#2

@krikhi
for 1 wrong ans, run the loop in line 10 till i<12, you missed i=11 in your code
your code is getting runtime error for 1 testcase because n is upto 10^9. You can’t make dp[n] when n >10^7.

#3

as I cant make DP array for n>10^7 so what should I do to optimise the space complexity

#4

Construct dp as you did till 10^7. Then to find ans of n, use recursive function with base case
if(n<10^7){ return dp[i]; }

#5

if n>10^7 then we will directly call the recursive func???

#6

make dp[10^7] global. construct it as you did in main function. your recursive function will be like
int find_ans(int n){
if(n<10000000){ return dp[n]; }
else{ return max(n, find_ans(n/2)+find_ans(n/3)+find_ans(n/4)); }
}

#7

Thanks for the help. All the testcases are passed

1 Like