algoadvance

Leetcode 365. Water and Jug Problem

Problem Statement

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

If targetCapacity liters of water is measurable, you must do it by using these operations:

  1. Fill any of the jugs completely with water.
  2. Empty any of the jugs.
  3. Pour water from one jug into another jug until one of the jugs is either full or empty.

Return true if targetCapacity liters can be measured using the two jugs, otherwise return false.

Clarifying Questions

  1. What are the constraints on jug1Capacity, jug2Capacity, and targetCapacity? Are they all non-negative integers?
  2. Can the targetCapacity be greater than the sum of jug1Capacity and jug2Capacity?
  3. Is it possible for any of the capacities (jug1Capacity, jug2Capacity, targetCapacity) to be zero?

With these clarifications in mind, let’s move on to defining the solution strategy.

Strategy

The problem boils down to a classic mathematical problem that can be solved using Bézout’s identity and the properties of the greatest common divisor (GCD).

Key Insight: A solution exists if and only if the targetCapacity is a multiple of the GCD of jug1Capacity and jug2Capacity, and targetCapacity does not exceed the sum of the two jug capacities.

Steps:

  1. Calculate the GCD of jug1Capacity and jug2Capacity.
  2. Check if targetCapacity is less than or equal to the sum of the two jug capacities.
  3. Verify if targetCapacity is a multiple of the GCD obtained.

Time Complexity:

Code

#include <algorithm> // for __gcd function

class Solution {
public:
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // If the target capacity is greater than the sum of both jugs, it's impossible
        if(targetCapacity > jug1Capacity + jug2Capacity) {
            return false;
        }
        
        // Calculate the GCD of both jug capacities
        int gcd = std::__gcd(jug1Capacity, jug2Capacity);
        
        // Check if targetCapacity is a multiple of GCD
        return targetCapacity % gcd == 0;
    }
};

Explanation:

  1. GCD Calculation: We use the built-in std::__gcd function to compute the GCD of jug1Capacity and jug2Capacity.
  2. Capacity Check: We first check if targetCapacity is greater than the total capacity of both jugs combined. If it is, then it’s impossible to measure that amount of water.
  3. Multiple of GCD Check: Finally, we validate if targetCapacity is a multiple of the GCD, which ensures it’s measurable by using the two jugs.

This completes our solution. The strategy leverages basic number theory to determine the feasibility of measuring the desired water capacity with two jugs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI