algoadvance

You are given two jugs with capacities jug1Capacity and jug2Capacity liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity liters using these two jugs.

The operations you can perform are:

  1. Fill any of the jugs completely.
  2. Empty any of the jugs.
  3. Pour water from one jug into the other until the other jug is completely full, or the first jug itself is empty.

Example 1

Input: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
Output: true

Example 2

Input: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
Output: false

Example 3

Input: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
Output: true

Clarifying Questions

  1. Are the jug capacities and the target always positive integers?
  2. Are there any constraints on the maximum size of the capacities or the target?
  3. Can both jugs be used simultaneously for pouring water, or only one operation can be performed at a time?
  4. Is there a specific format in which the output should be returned?

Strategy

This problem is equivalent to the classic water jug problem, which can be solved using the properties of greatest common divisors (GCD). According to Bézout’s identity, for any integers a and b, if d is the GCD of a and b, there exist integers x and y such that ax + by = d. For this problem, the target capacity (targetCapacity) must be a multiple of the GCD of the two jug capacities (jug1Capacity and jug2Capacity), and must not exceed the sum of both jugs’ capacities.

The conditions to return True are:

  1. targetCapacity is less than or equal to the sum of both jugs’ capacities.
  2. targetCapacity is a multiple of the GCD of jug1Capacity and jug2Capacity.

Let’s write the code to implement this solution.

Code

import math

def canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity):
    if targetCapacity > jug1Capacity + jug2Capacity:
        return False
    if targetCapacity % math.gcd(jug1Capacity, jug2Capacity) == 0:
        return True
    return False

# Test cases
print(canMeasureWater(3, 5, 4))  # Expected output: True
print(canMeasureWater(2, 6, 5))  # Expected output: False
print(canMeasureWater(1, 2, 3))  # Expected output: True

Time Complexity

The time complexity of this solution is constant, O(1), because:

  1. Calculating the GCD of two numbers using the Euclidean algorithm takes constant time.
  2. Dividing the target capacity by the GCD also takes constant time.

Thus, the overall complexity is O(1), making this approach highly efficient.

Try our interview co-pilot at AlgoAdvance.com