this is problem link in spoj on minimum coin change
and this is my solution link but it is not passing on spoj please look into this…
Coin change problem
u can refer to this video, it goes through the entire explanation as well as the code
it gets submitted on leetcode and will also be submitted on spoj
But i want correction in my code can you explain what mistake I have done?? Because it passed on gfg but not in spoj??
Honestly, geeksforgeeks has really weak test cases, i feel the logic is faulty, there is a major mistake in checking for conditions
i mean the logic is not entirely wrong but won’t be able to handle a lot of cases due to the order in which it checks for things
int
minCoins(
int
coins[],
int
m,
int
V)
{
// base case
if
(V == 0)
return
0;
// Initialize result
int
res = INT_MAX;
// Try every coin that has smaller value than V
for
(
int
i=0; i<m; i++)
{
if
(coins[i] <= V)
{
int
sub_res = minCoins(coins, m, V-coins[i]);
// Check for INT_MAX to avoid overflow and see if
// result can minimized
if
(sub_res != INT_MAX && sub_res + 1 < res)
res = sub_res + 1;
}
}
return
res;
}
u can refer to this function