C++ Solution using number theory WITH explanation


  • 0
    U

    Basic idea:

    • if z > x + y it's impossible to solve it.
    • otherwise it's equivalent to find ax + by = z, which is equivalent to whether z mod gcd(x, y) = 0 by Bezout's Theorem in number theory.
    • take care of the annoying corner case input which may cause mod 0 exception.
    class Solution {
    public:
        int gcd(int x, int y) {
            if (x < y) {
                x += y;
                y = x - y;
                x -= y;
            }
            while (y) {
                x %= y;
                x += y;
                y = x - y;
                x -= y;
            }
            return x;
        }
    
        bool canMeasureWater(int x, int y, int z) {
            if (x + y < z)
                return false;
            if (x + y == 0)
                return (z == 0);
            return (z % gcd(x, y) == 0);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.