FastPrep
Problem · Dynamic Programming

Minimum Coins for a Target

Learn this problem
● Mediuminfosys logoinfosysNEW GRADONSITE INTERVIEW

Problem statement

Given an integer array coins of positive denominations and a nonnegative integer target, return the minimum number of coins needed to sum exactly to target.

You may use each denomination any number of times. Return -1 when no combination reaches the target. A target of 0 requires 0 coins.

Function

minCoins(coins: int[], target: int) → int

Examples

Example 1

coins = [1,2,5]target = 11return = 3

The target can be formed as 5 + 5 + 1, using three coins, and no two-coin combination reaches 11.

Example 2

coins = [2]target = 3return = -1

No number of coins with denomination 2 can sum to 3.

Example 3

coins = [2,3]target = 0return = 0

The empty selection already has sum 0.

Constraints

  • 1 <= coins.length <= 200
  • 1 <= coins[i] <= 100000
  • 0 <= target <= 100000
  • Duplicate denominations may appear in coins.

More infosys problems

drafts saved locally
public int minCoins(int[] coins, int target) {
  // write your code here
}
coins[1,2,5]
target11
expected3
checking account