Water and Jug Problem

Description

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

Solution(javascript)

// /** 1: gcd
//  * @param {number} x
//  * @param {number} y
//  * @param {number} z
//  * @return {boolean}
//  */
// const canMeasureWater = function (x, y, z) {
//   const gcd = (a, b) => {
//     if (b < a) {
//       return gcd(b, a)
//     }
//     if (a === 0) {
//       return b
//     }
//     return gcd(b % a, a)
//   }
//   if (x + y < z) {
//     return false
//   }
//   if (x === z || y === z || x + y === z) {
//     return true
//   }
//   return z % gcd(x, y) === 0
// }


/** 1: bfs
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
const canMeasureWater = function (x, y, z) {
  let current = [0]
  const visited = {
    0: true,
  }
  if (x + y < z) {
    return false
  }
  if (x === z || y === z || z + y === z) {
    return true
  }
  while (current.length > 0) {
    const next = []
    const push = (num) => {
      if (!visited[num]) {
        visited[num] = true
        next.push(num)
      }
    }
    for (const num of current) { // num 为 x,y 组合可能取得的值
      if (num === z) {
        return true
      }
      if (num + x <= x + y) {
        push(num + x)
      }
      if (num + y <= x + y) {
        push(num + y)
      }
      if (num - y >= 0) {
        push(num - y)
      }
      if (num - x >= 0) {
        push(num - x)
      }
    }
    current = next
  }
  return false
}