Coin Change Minimum Coins in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum coins for amount 11

What is the output of the following TypeScript code that finds the minimum number of coins needed to make amount 11 using coins [1, 2, 5]?

DSA Typescript

function minCoins(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(minCoins([1, 2, 5], 11));

A 3

B 4

C 5

D -1

💡 Hint

Think about how many coins of 5, 2, and 1 can sum to 11 with minimum count.

The minimum coins to make 11 using [1, 2, 5] are 3 coins: 5 + 5 + 1.

❓ Predict Output

intermediate

Output when no solution exists

What is the output of this TypeScript code when trying to make amount 3 with coins [2, 4]?

DSA Typescript

function minCoins(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(minCoins([2, 4], 3));

A 1

B -1

C 0

D 3

💡 Hint

Check if amount 3 can be formed by any combination of 2 and 4.

Amount 3 cannot be formed using coins 2 and 4, so the function returns -1.

🔧 Debug

advanced

Identify the bug in coin change code

The following TypeScript code is intended to find the minimum number of coins needed for a given amount. What is the bug causing incorrect results?

DSA Typescript

function minCoins(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(0);
  for (let i = 1; i <= amount; i++) {
    dp[i] = Infinity;
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(minCoins([1, 3, 4], 6));

A Return statement should check for dp[0] instead of dp[amount]

B Loop should start from i = 0 instead of 1

C dp array initialized with zeros causes wrong base case

D Coins array should be sorted before processing

💡 Hint

Check how dp array is initialized and how it affects calculations.

The dp array is initialized with zeros, so dp[0] = 0 but other dp[i] are also zero initially, which is incorrect. They should be initialized to Infinity except dp[0].

🧠 Conceptual

advanced

Time complexity of coin change minimum coins algorithm

What is the time complexity of the dynamic programming solution for the coin change minimum coins problem with n coins and amount m?

A O(n * m)

B O(n + m)

C O(n^m)

D O(m^n)

💡 Hint

Consider nested loops over coins and amounts.

The algorithm uses two nested loops: one over the amount (m) and one over the coins (n), resulting in O(n * m) time complexity.

🚀 Application

expert

Minimum coins with unlimited and limited coin usage

Given coins [1, 3, 4] and amount 6, what is the minimum number of coins needed if coin 3 can only be used once, but others unlimited?

A 2

B -1

C 4

D 3

💡 Hint

Think about using coin 3 once and then filling the rest with 1 or 4.

Using coin 3 once, the remaining amount is 3. Minimum coins for 3 using 1 and 4 is 3 (1+1+1). Total coins = 1 + 3 = 4 is wrong. But better is using 4 once and 1 twice: 4 + 1 + 1 = 6 with 3 coins total. Since coin 3 can be used once, best is 3 coins.