Minimum umbrellas to cover an exact distance

Coding Challenges
, , ,
1

Problem. Umbrellas come in fixed sizes. You may use any size as many times as you like, but the total covered distance must equal distance exactly.

Return the minimum number of umbrellas needed, or -1 if no exact combination exists.

Examples:

  • sizes = [2, 3, 5], distance = 7 → 2 using 2 + 5
  • sizes = [3, 5], distance = 7 → -1

This is an unbounded coin change problem.

Solution. Let dp[target] be the minimum umbrellas needed to cover exactly target.

  • dp[0] = 0
  • for each target, try every umbrella size that can end the solution
  • take the best valid predecessor
def minimum_umbrellas(sizes, distance):
	sizes = sorted(sizes)
	inf = distance + 1
	dp = [0] + [inf] * distance

	for target in range(1, distance + 1):
		for size in sizes:
			if size > target:
				break
			candidate = dp[target - size] + 1
			if candidate < dp[target]:
				dp[target] = candidate

	return -1 if dp[distance] == inf else dp[distance]

Runtime is O(len(sizes) * distance). Extra space is O(distance).

Gotchas.

  • This is exact coverage, not at-least coverage.
  • Use a sentinel like distance + 1 or inf for unreachable states.
  • Sorting sizes lets you stop early once size > target.

Run: minimum umbrellas