365. Water and Jug Problem – Leetcode Solutions

Example 1:

Input: x = 3, y = 5, target = 4

Output: true

Explanation:

Follow these steps to reach a total of 4 liters:

Fill the 5-liter jug (0, 5).
Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
Empty the 3-liter jug (0, 2).
Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
Fill the 5-liter jug again (2, 5).
Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).
Reference: The Die Hard example.

Example 2:

Input: x = 2, y = 6, target = 5

Output: false

Example 3:

Input: x = 1, y = 2, target = 3

Output: true

Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        # If the target is greater than the sum of both jug capacities, it's impossible to measure
        if target > x + y:
            return False
        
        # Check if the target is a multiple of the GCD of x and y
        return target % math.gcd(x, y) == 0

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        // If the target is more than the sum of both jugs' capacities, it's impossible.
        if (x + y < target) return false;

        // Special cases where the target is 0 or exactly matches one of the jug capacities
        if (target == 0 || target == x || target == y || target == x + y) return true;

        // Use a BFS approach to explore all possible states of the jugs.
        std::queue<std::pair<int, int>> q; // To track the amount of water in the two jugs
        std::set<std::pair<int, int>> visited; // To avoid revisiting the same state

        // Start from the initial state where both jugs are empty
        q.push({0, 0});
        visited.insert({0, 0});

        while (!q.empty()) {
            auto [currX, currY] = q.front();
            q.pop();

            // If either of the jugs contains the target amount of water, return true.
            if (currX == target || currY == target || currX + currY == target) {
                return true;
            }

            // List of all possible states from the current state
            std::vector<std::pair<int, int>> nextStates = {
                {x, currY},          // Fill the first jug completely
                {currX, y},          // Fill the second jug completely
                {0, currY},          // Empty the first jug
                {currX, 0},          // Empty the second jug
                {std::max(0, currX - (y - currY)), std::min(y, currX + currY)}, // Pour from jug1 to jug2
                {std::min(x, currX + currY), std::max(0, currY - (x - currX))}  // Pour from jug2 to jug1
            };

            // Explore all the next states
            for (auto state : nextStates) {
                if (visited.find(state) == visited.end()) {
                    visited.insert(state);
                    q.push(state);
                }
            }
        }

        // If no valid configuration leads to the target, return false.
        return false;
    }
};

var canMeasureWater = function(x, y, target) {
    // Step 1: If the total capacity of both jugs is less than the target, it's impossible to measure the target
    if (x + y < target) {
        return false;
    }

    // Step 2: If either jug has a capacity equal to or greater than the target, it's possible to measure the target
    if (x === target || y === target || x + y === target) {
        return true;
    }

    // Step 3: Use the greatest common divisor (GCD) to determine if the target is measurable.
    // If the target is a multiple of the GCD of the two jugs' capacities, it's possible to measure the target.
    const gcd = (a, b) => {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    };

    // Step 4: Check if target can be measured as a multiple of GCD(x, y)
    return target % gcd(x, y) === 0;
};

class Solution {
    /**
     * This function checks if it's possible to measure exactly 'target' liters using two jugs with capacities 'x' and 'y'.
     *
     * @param x - Capacity of the first jug in liters.
     * @param y - Capacity of the second jug in liters.
     * @param target - The target amount of water we need to measure.
     * @return boolean - Returns true if it's possible to measure exactly 'target' liters, otherwise false.
     */
    public boolean canMeasureWater(int x, int y, int target) {
        // Step 1: If the total capacity of both jugs is less than the target, it's impossible to measure the target.
        if (x + y < target) {
            return false;
        }

        // Step 2: If either jug has a capacity equal to or greater than the target, or their total equals the target, return true.
        if (x == target || y == target || x + y == target) {
            return true;
        }

        // Step 3: Use the greatest common divisor (GCD) to determine if the target is measurable.
        // If the target is a multiple of the GCD of the two jugs' capacities, it's possible to measure the target.
        return target % gcd(x, y) == 0;
    }

    /**
     * Helper function to calculate the greatest common divisor (GCD) of two numbers.
     * We use the Euclidean algorithm to find the GCD.
     *
     * @param a - The first number.
     * @param b - The second number.
     * @return int - The GCD of a and b.
     */
    private int gcd(int a, int b) {
        // Apply Euclidean algorithm to find the GCD
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}