LeetCode 365: Water and Jug Problem Solution

Master LeetCode problem 365 (Water and Jug Problem), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

365. Water and Jug Problem

Medium

Math Depth-First Search Breadth-First Search

Problem Explanation

Explanation:

To solve this problem, we can use the concept of the "Bézout's identity" theorem which states that for given non-negative integers a and b, there exist integers x and y such that ax + by = d (where d is the greatest common divisor of a and b). In this problem, if the target amount of water is reachable, it must be a multiple of the greatest common divisor of x and y. We can find this greatest common divisor using the Euclidean algorithm.

Here is how the algorithm works:

Check if the target amount is less than or equal to the sum of the jug capacities x and y. If not, return false as the target is unreachable.
Find the greatest common divisor (gcd) of x and y using the Euclidean algorithm.
Check if the target amount is divisible by the gcd. If yes, return true; otherwise, return false.

Time complexity: O(log(min(x, y))) Space complexity: O(1)

Solution Code

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) {
            return false;
        }
        
        return target == 0 || (target % gcd(x, y) == 0);
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 365 (Water and Jug Problem)?

This page provides optimized solutions for LeetCode problem 365 (Water and Jug Problem) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 365 (Water and Jug Problem)?

The time complexity for LeetCode 365 (Water and Jug Problem) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 365 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 365 in Java, C++, or Python.

Back to LeetCode Solutions