LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 该问题相当于判断如下整数方程是否有解

a * jug1Capacity + b * jug2Capacity = targetCapacity

• 由 裴蜀定理（Bézout’s identity），方程有解的条件为 targetCapacity 能被 a 和 b 的最大公约数整除

class Solution {
 public:
  bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    if (targetCapacity > jug1Capacity + jug2Capacity) {
      return false;
    }
    return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
  }
};