Math solution - Java solution


  • 100
    H

    This is a pure Math problem. We need the knowledge of number theory to cover the proof and solution. No idea why microsoft uses this problem in real interview.

    The basic idea is to use the property of Bézout's identity and check if z is a multiple of GCD(x, y)

    Quote from wiki:

    Bézout's identity (also called Bézout's lemma) is a theorem in the elementary theory of numbers:

    let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x
    and y such that ax+by=d

    In addition, the greatest common divisor d is the smallest positive integer that can be written as ax + by

    every integer of the form ax + by is a multiple of the greatest common divisor d.

    If a or b is negative this means we are emptying a jug of x or y gallons respectively.

    Similarly if a or b is positive this means we are filling a jug of x or y gallons respectively.

    x = 4, y = 6, z = 8.

    GCD(4, 6) = 2

    8 is multiple of 2

    so this input is valid and we have:

    -1 * 4 + 6 * 2 = 8

    In this case, there is a solution obtained by filling the 6 gallon jug twice and emptying the 4 gallon jug once. (Solution. Fill the 6 gallon jug and empty 4 gallons to the 4 gallon jug. Empty the 4 gallon jug. Now empty the remaining two gallons from the 6 gallon jug to the 4 gallon jug. Next refill the 6 gallon jug. This gives 8 gallons in the end)

    See wiki:

    Bézout's identity

    and comments in the code

    public boolean canMeasureWater(int x, int y, int z) {
        //limit brought by the statement that water is finallly in one or both buckets
        if(x + y < z) return false;
        //case x or y is zero
        if( x == z || y == z || x + y == z ) return true;
        
        //get GCD, then we can use the property of Bézout's identity
        return z%GCD(x, y) == 0;
    }
    
    public int GCD(int a, int b){
        while(b != 0 ){
            int temp = b;
            b = a%b;
            a = temp;
        }
        return a;
    }
    

  • 3

    BUG in your code.
    see this case x = 4, y = 6, z = 8.

    you should not check if GCD(x, y) == 1, but check if z is a mulitple of GCD(x, y)


  • 2
    H

    I am stuipd. THX bro, please check my solution again


  • 30
    T

    i think this problem is microsoft's way of saying no to their candidates.


  • 1
    M

    Since GDC function will return y if x == 0 only or x if y == 0 only, I think we only need the condition below,

    if (x + y == z) return true;
    

  • 0
    C

    Nice solution, this is my Python version of it:

    def canMeasureWater(x, y, z):
        def gcd(x, y):
                while x:
                    x, y = y % x, x
                return y
    
        return z == x+ y or (z < x + y and z % gcd(x, y) == 0)

  • 0

    Thanks, I have added this test case.


  • 0
    A

    Totally agree with @triployd. Struggled a log with recursive solutions though unsuccessfully. Even knowing this Bézout's lemma it's not intuitive from the start that it suits to this practical problem. And also not sure why it's marked as "medium"...


  • 0
    A

    I think we don't need to check x+y==z, since that's z = ax+by where a=1, b=1. Only exception is x==0 and y==0 but that's handled by x==z || y==z


  • 2

    Thanks for sharing such wonderful idea.

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

  • 2

    @hpplayer said in Math solution - Java solution:

    No idea why microsoft uses this problem in real interview.

    I guess that one should be at least able to design a bruteforce solution, like @leetcodedavy did here here. Then, I guess the interviewer will help you figure out the GCD solution.


  • 2
    R

    @triployd who wants to work for MS anyway?


  • 0
    T

    what is the time complexity of this algorithm?


  • 1

    @thalaivva Clearly O(1), it's a math solution.


  • 0
    D

    @LHearen Since there is a loop in GCD shouldn't it be O(x/z)?


  • 0

    @delgado Can be ignored -> O(1), uncorrelated to n.


  • 2
    D

    @LHearen Since the amount of loops that occur in GCD is dependent on the values of x and y, it is inaccurate to say that the time complexity is O(1). if x = 3 and y = 3 then the loop in GCD will only run once. x = 3, y = 15 would loop twice. Therefore, the complexity is not constant.

    The complexity I stated earlier was inaccurate so I did some more research. See this post for the run-time of the Euclidean algorithm:
    http://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm


  • 0

    @delgado O(log min(a, b)) is a good upper bound as that post pointed out, so here since the max can never be bigger than 2^32 then it should be constant, right?


  • 1
    D

    @LHearen I am not sure if that logic holds. For example suppose we have the following function:

    void printHi(int x) {
    	while(x > 0) {
    		print("Hi");
                    x--;
    	}
    }
    
    

    Do we say the time complexity is O(1) since we know that x < 2^32? We would still say O(n) because there could theoretically be a better algorithm that is more efficient with the same values of x.


  • 0

    @delgado The post you provided clearly mentioned the steps of that is under O(log(min(a,b)) and since each step we just do O(1) calculation and as a result the whole time complexity is then O(log(min(a,b)), so how could you now give us this example to testify your point?


Log in to reply
 

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