LeetCode //C - 365. Water and Jug Problem

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:

1. // Helper function to compute the greatest common divisor
2. int gcd(int a, int b) {
3.     while (b != 0) {
4.         int temp = b;
5.         b = a % b;
6.         a = temp;
7.     }
8.     return a;
9. }
11. bool canMeasureWater(int x, int y, int target) {
12.     // If target is greater than the sum of both jugs, it's not possible
13.     if (target > x + y) {
14.         return false;
15.     }
16.    
17.     // If target is zero, it's always possible (no need to fill any jug)
18.     if (target == 0) {
19.         return true;
20.     }
21.    
22.     // Calculate the greatest common divisor of x and y
23.     int g = gcd(x, y);
24.    
25.     // Check if target is a multiple of the gcd of x and y
26.     return target % g == 0;
27. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。