首页 > 代码库 > 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 = 4Output: True
Example 2:
Input: x = 2, y = 6, z = 5Output: False
Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases.
Analysis:
It is a number theory problem.
https://discuss.leetcode.com/topic/49238/math-solution-java-solution/2
Solution:
public class Solution { public boolean canMeasureWater(int x, int y, int z) { if (x+y < z) return false; if (x==z || y==z || x+y==z) return true; return z%GCD(x,y)==0; } public int GCD(int x, int y){ while (x%y!=0){ int temp = x; x = y; y = temp%y; } return y; }}
LeetCode-Water and Jug Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。