365. Water and Jug Problem

// (1) BFS
class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        
        int[] directions = {x, -x, y, -y};
        Deque q = new ArrayDeque<>();
        q.offer(0);
        Set visited = new HashSet<>();
        visited.add(0);
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == z) return true;
            for (int direction : directions) {
                int total = direction + cur;
                if (total == z) return true;
                if (total < 0 || total > x + y) continue;
                if (!visited.contains(total)) {
                    visited.add(total);
                    q.offer(total);
                }
            }
        }
        
        return false;
    }
}

// (2) Math
class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        
        return z % gcd(x, y) == 0;
    }
    
    private int gcd(int x, int y) {
        if (y == 0) return x;
        return gcd(y, x % y);
    }
}