Ambiguous Measurements

Tags

Ambiguous Measurements

Category

Recursion

Difficulty

Very Hard

Problem Statement

You are given a list of measuring cups, where each cup has a low and high mark representing a range of liquid it can measure (e.g., a cup with marks [200, 210] measures between 200 and 210 ml). You are also given a target range [low, high]. Determine whether it is possible to measure an amount of liquid that falls within the target range by using any combination of cups (each cup can be used any number of times). Each time you pour from a cup, you add somewhere between its low and high amount to the total.

Intuition

Each pour adds an uncertain amount within a range. After multiple pours, the total lies within the sum of the individual ranges: the minimum total is the sum of all low marks, and the maximum total is the sum of all high marks. We need to determine if there is some combination of pours such that the resulting range [totalLow, totalHigh] overlaps with the target [targetLow, targetHigh]. Specifically, we need totalLow <= targetHigh and totalHigh >= targetLow. The problem has overlapping subproblems (many paths lead to the same remaining range), making it suitable for memoized recursion.

Approach

  1. Define a recursive function canMeasure(low, high) that returns whether we can reach the target range starting from an accumulated range of [low, high].
  2. Base case: If low > targetHigh, we have overshot and cannot succeed — return false. If low >= targetLow and high <= targetHigh, the current range is entirely within the target — return true.
  3. Recursive case: Try adding each cup. For cup with range [cupLow, cupHigh], recurse on canMeasure(low + cupLow, high + cupHigh).
  4. Memoize on the (low, high) pair to avoid recomputation.
  5. Start with canMeasure(0, 0).

Pseudocode

function ambiguousMeasurements(cups, target):
    memo = {}
    return canMeasure(0, 0, cups, target, memo)

function canMeasure(low, high, cups, target, memo):
    if (low, high) in memo:
        return memo[(low, high)]

    if low > target[1]:  # overshot
        memo[(low, high)] = false
        return false

    if low >= target[0] and high <= target[1]:  # within target
        memo[(low, high)] = true
        return true

    if high > target[1]:  # high end exceeds target, can't fix
        memo[(low, high)] = false
        return false

    for cup in cups:
        if canMeasure(low + cup[0], high + cup[1], cups, target, memo):
            memo[(low, high)] = true
            return true

    memo[(low, high)] = false
    return false

Time & Space Complexity

  • Time: O(low * high * c) where low and high represent the range of possible accumulated values up to the target bounds, and c is the number of cups. The memoization table has at most O(low * high) entries, and each entry tries c cups.
  • Space: O(low * high) for the memoization table, plus O(target / minCup) recursion depth in the worst case.

Key Insights

  • The problem is fundamentally about reachability in a 2D state space where the state is (accumulatedLow, accumulatedHigh).
  • The pruning condition high > target[1] is critical: once the high end of our range exceeds the target high, adding more liquid only makes it worse. This prevents infinite recursion.
  • Each cup can be used any number of times, making this an unbounded knapsack-style problem.
  • The ranges only grow (both low and high increase with each pour), so we are guaranteed to eventually exceed the target and terminate.
  • Memoization is essential because different orderings of cup pours can lead to the same (low, high) state.

Edge Cases

  • Single cup whose range falls entirely within the target: one pour suffices.
  • No cups can reach the target even individually: may need multiple pours.
  • Target range is [0, 0]: achievable by pouring nothing (0 pours).
  • Cup ranges that overlap heavily: more combinations reach the target.
  • All cups have the same low and high (exact measurement): reduces to checking if any multiple of that value falls in the target range.
  • Target low equals target high: must achieve an exact amount, which is only possible if the total range includes that exact value.

Linked mentions