Water and jug problem

Math Depth-First Search Breadth-First Search

45.0% acceptance

Jan 12, 2026

1675

1514

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_measure_water(x: i32, y: i32, target: i32) -> bool {
    if target > x + y {
      return false;
    }
    if target == x || target == y || target == x + y {
      return true;
    }
    
    fn gcd(mut a: i32, mut b: i32) -> i32 {
      while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
      }
      a
    }
    
    target % gcd(x, y) == 0
  }
}