365. Water and Jug Problem
You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:
- Fill either jug completely with water.
- Completely empty either jug.
- Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.
Example 1:
Input: x = 3, y = 5, target = 4
Output: true
Explanation:
Follow these steps to reach a total of 4 liters:
- Fill the 5-liter jug (0, 5).
- Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
- Empty the 3-liter jug (0, 2).
- Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
- Fill the 5-liter jug again (2, 5).
- Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
7.Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).
Reference: The Die Hard example.
Example 2:
Input: x = 2, y = 6, target = 5
Output: false
Example 3:
Input: x = 1, y = 2, target = 3
Output: true
Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.
Constraints:
- 1 < = x , y , t a r g e t < = 1 0 3 1 <= x, y, target <= 10^3 1<=x,y,target<=103
From: LeetCode
Link: 365. Water and Jug Problem
Solution:
Ideas:
- gcd Function: Computes the greatest common divisor using the Euclidean algorithm.
- canMeasureWater Function:
- First checks if target is achievable given the capacities of the two jugs.
- Then checks if target is a multiple of the GCD of the jug capacities.
Code:
- // Helper function to compute the greatest common divisor
- int gcd(int a, int b) {
- while (b != 0) {
- int temp = b;
- b = a % b;
- a = temp;
- }
- return a;
- }
- bool canMeasureWater(int x, int y, int target) {
- // If target is greater than the sum of both jugs, it's not possible
- if (target > x + y) {
- return false;
- }
-
- // If target is zero, it's always possible (no need to fill any jug)
- if (target == 0) {
- return true;
- }
-
- // Calculate the greatest common divisor of x and y
- int g = gcd(x, y);
-
- // Check if target is a multiple of the gcd of x and y
- return target % g == 0;
- }
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |