365. 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 = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

 

Constraints:

  • 0 <= x <= 10^6
  • 0 <= y <= 10^6
  • 0 <= z <= 10^6

Rust Solution

struct Solution;
use std::collections::VecDeque;

impl Solution {
    fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
        if z > x + y {
            return false;
        }
        if z == x || z == y || z == x + y {
            return true;
        }
        let mut visited = vec![false; (x + y) as usize];

        let mut queue: VecDeque<i32> = VecDeque::new();
        queue.push_back(0);
        while let Some(front) = queue.pop_front() {
            for diff in [x, y, -x, -y].iter() {
                let next = front + diff;
                if next == z {
                    return true;
                } else {
                    if next < x + y && next > 0 && !visited[next as usize] {
                        visited[next as usize] = true;
                        queue.push_back(next);
                    }
                }
            }
        }
        false
    }
}

#[test]
fn test() {
    let x = 3;
    let y = 5;
    let z = 4;
    let res = true;
    assert_eq!(Solution::can_measure_water(x, y, z), res);
    let x = 2;
    let y = 6;
    let z = 5;
    let res = false;
    assert_eq!(Solution::can_measure_water(x, y, z), res);
}

Having problems with this solution? Click here to submit an issue on github.