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
Solution: Math
special case 1: x == z or y == z or x + y == z: return True
special case 2: x + y < z: return False
normal case: z must be a factor of gcd(x, y)
Time complexity: O(log(min(x, y))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 |
// Author: Huahua class Solution { public: bool canMeasureWater(int x, int y, int z) { if (x == z || y == z || x + y == z) return true; if (x + y < z) return false; return z % gcd(x, y) == 0; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment