LeetCode Water and Jug Problem

LeetCode Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

  • Fill any of the jugs completely with water.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

很有意思的水罐问题。给定一个3L的水罐和一个5L的水罐和无限的水,问怎样才能得到4L的水。

这个例子很常见了,可以这样做:

  1. 盛满5L水罐;
  2. 将5L水罐中的水导入3L水罐,此时5L水罐中还剩2L水;
  3. 将3L水罐中的水清空;
  4. 将5L水罐中的2L水倒入3L水罐中;
  5. 盛满5L水罐;
  6. 将5L水罐中的水倒入3L水罐中,此时5L水罐中剩余4L水,3L水罐中是满的;
  7. 将3L水罐中的水清空,此时只剩5L水罐中的4L水。

但是遇到一般的x、y、z时,怎样解呢,这里面肯定暗含某种数学规律,看了题解才恍然大悟

将问题转换为这样一个问题:给定xL和yL水罐和无限的水,以及一起无穷大的水罐,怎样利用x和y才能在无穷大的水罐中盛满zL的水。假设我们要往无穷大的水罐中倒m次xL的水和n次yL的水,则有mx+ny=z,如果m为正,则是倒入,为负则是舀出。比如x=3, y=5, z=4时,有(-2)*3+2*5=4,表示往无穷大的水罐中倒入2次5L的水,并且舀出2次3L的水,剩余正好4L。而上面的7步正好也包含2次盛满5L水,2次清空3L水。

所以问题就转换为方程mx+ny=z对于m,n是否有整数解。这需要用到裴蜀定理,又是头一回听说。

假设x和y的最大公约数是d=gcd(x,y),如果z是d的整数倍,则上式有整数解。所以问题就好办了,求一下x,y的最大公约数,然后判断z是否是最大公约数的整数倍就好了。

另外要保证x+y>=z,因为如果x和y加起来的容量都没有z大,怎么可能使得两个罐中水量之和正好等于z呢。

代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x%y);
	}
public:
	bool canMeasureWater(int x, int y, int z) {
		return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
	}
};

本代码提交AC,用时0MS。

Leave a Reply

Your email address will not be published. Required fields are marked *