322. Coin Change Leetcode Solution
Coin Change Leetcode Problem :
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Coin Change Leetcode Solution :
Constraints :
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 – 1
- 0 <= amount <= 10^4
Example 1:
- Input: coins = [2], amount = 3
- Output: -1
Example 2:
- Input: coins = [1], amount = 0
- Output: 0
Intuition :
Although, the problem seems to have greedy approach as a candidate solution, this problem really needs a dynamic programming approach.
Approach :
Let c1, c2, …, ck be denominations of the k coins. Then, the amount may be arrived at by adding one more coin of the respective denomination from (amount – c1), (amount – c2), …, (amount – ck). Our job is to pick the node that needed the fewest number of coins to get to. This problem has an optimal sub-structure.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int coinChange(vector< int>& coins, int amount) {
table[0] = 0;
for (auto i = 1; i < amount + 1; ++i) {
for (auto coin : coins) {
if (auto cAmt = i - coin; cAmt >= 0) {
table[i] = min(table[i], table[cAmt]);
}
}
if (table[i] != INT_MAX) {
table[i] = table[i] + 1;
}
}
if (INT_MAX == table.back()) {
return -1;
}
return table.back();
}
};
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
for (int i = 1; i< = amount;i++)
{
int min = Integer.MAX_VALUE;
for (int j = 0; j< coins.length;j++)
{
if (i>=coins[j] && dp[i - coins[j]] !=-1)
{
min = Math.min(min,dp[i - coins[j]]);
}
}
dp[i] = (min == Integer.MAX_VALUE) ? -1 : 1+min;
}
return dp[amount];
}
}
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
count, prev = 0, 1 << amount
while prev & 1 == 0:
curr = prev
for coin in coins:
curr |= prev >> coin
if curr == prev:
return -1
count += 1
prev = curr
return count
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment