C++、 java 、python solutions, using Euclidean Algorithm


  • 0
    C

    Thanks to yular's solutions (https://leetcode.com/discuss/110235/c-solution-using-euclidean-algorithm)
    Thanks to qgambit2's solutions (https://leetcode.com/discuss/110378/java-solution-based-on-modulus-property).

    Find the common divisor of x and y, if z is If z is a multiple of the number of convention or z equals x, or y, or x + y or 0. This is the answer.

    c++ solution

    class Solution {
    public:
        bool canMeasureWater(int x, int y, int z) {
            if (z==x+y || z==x || z==y || z==0)
                return true;
            if (x==0 || y==0 || z>x+y || z%gcd(x, y)!= 0)
                return false;
            return true;
        }
        
    private:
        int gcd(int a, int b){
            return b == 0? a : gcd(b, a%b);
        }
    };
    

    java solution

    public class Solution {
        public boolean canMeasureWater(int x, int y, int z) {
            if (z==x+y || z==x || z==y || z==0)
                return true;
            if (x==0 || y==0 || z>x+y || z%gcd(x, y)!= 0)
                return false;
            return true;
        }
        private int gcd(int a, int b){
            return b == 0? a : gcd(b, a%b);
        }
    }
    

    python solution

    class Solution(object):
        def canMeasureWater(self, x, y, z):
            """
            :type x: int
            :type y: int
            :type z: int
            :rtype: bool
            """
            if z == x+y or z == x or z == y or z == 0:
                return True
            if x == 0 or y == 0 or z > x+y or z%self.gcd(x, y) != 0:
                return False
            return True
            
        def gcd(self, a, b):
            return a if b == 0 else self.gcd(b, a%b)

  • 0
    N

    Maybe gcd can be done in a faster way

    int gcd(int  a,int b){
        while((a%=b)&&(b%=a));
        return a|b;
    }
    //belows are mine
    class Solution {
    public:
        bool canMeasureWater(int x, int y, int z) {
            if(z>x+y) return false;
            if((x|y)==0) return z==0;
            if(y==0) return (z%x)==0;
            while((x%=y)&&(y%=x));
            return (z%(x|y))==0;
        }
    };
    

Log in to reply
 

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