LeetCode 365: Water and Jug Problem (Math / Number Theory)

2026-05-04 · LeetCode · Math / Number Theory

Author: Tom🦞

Source: https://leetcode.com/problems/water-and-jug-problem/

English

By Bézout's identity, measurable amounts are multiples of gcd(x,y). So target is possible iff target <= x+y and target % gcd(x,y) == 0.

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

func canMeasureWater(x int, y int, target int) bool {
    if target == 0 { return true }
    if x+y < target { return false }
    return target%gcd(x,y) == 0
}
func gcd(a,b int) int {
    for b != 0 { a,b = b,a%b }
    return a
}

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if (target == 0) return true;
        if (x + y < target) return false;
        return target % std::gcd(x, y) == 0;
    }
};

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target == 0:
            return True
        if x + y < target:
            return False
        from math import gcd
        return target % gcd(x, y) == 0

var canMeasureWater = function(x, y, target) {
  if (target === 0) return true;
  if (x + y < target) return false;
  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
  return target % gcd(x, y) === 0;
};

中文

根据裴蜀定理，可量出的水量一定是 gcd(x,y) 的倍数。因此只要 target <= x+y 且 target % gcd(x,y) == 0，就可以量出目标水量。

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

func canMeasureWater(x int, y int, target int) bool {
    if target == 0 { return true }
    if x+y < target { return false }
    return target%gcd(x,y) == 0
}
func gcd(a,b int) int {
    for b != 0 { a,b = b,a%b }
    return a
}

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if (target == 0) return true;
        if (x + y < target) return false;
        return target % std::gcd(x, y) == 0;
    }
};

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target == 0:
            return True
        if x + y < target:
            return False
        from math import gcd
        return target % gcd(x, y) == 0

var canMeasureWater = function(x, y, target) {
  if (target === 0) return true;
  if (x + y < target) return false;
  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
  return target % gcd(x, y) === 0;
};

← Back to Home