Trying to solve this with strategy, not math


  • 0
    Y

    Apart from the GCD solution many have discussed, can we solve this with some strategy?

    I didn't know the math solution, and tried to see if I can find some patterns.

    1 ) let's first have two jugs with similar sizes, say, 15 and 18. Of course we can measure the diff 3. Then our strategy is, try to repeatedly pour water from smaller jug into bigger jug until full. That is:

    pour 15 units water into jug of size 18, pour again until full -> 12 left in the smaller jug
    pour 12 units water into jug of size 18, pour again until full -> 9 left in the smaller jug
    pour 9 units water into jug of size 18, pour again until full -> 6 left in the smaller jug
    pour 6 units water into jug of size 18, pour again until full -> 3 left in the smaller jug

    That 3 is what we need to stop - when we see a number the second time, we know we can't measure anything else.
    So, we have:

    15 18: 3 12 9 6 3
    

    Can we observe this pattern with other jugs? We can:

    15 17: 2 13 11 9 7 5 3 1 14 12 10 8 6 4 2
    15 19: 4 11 7 3 14 10 6 2 13 9 5 1 12 8 4
    

    2 ) When we have two jugs, one big one small, the strategy is a bit different. Say we have 4 and 14. Our strategy is, try to pour water repeatedly from bigger jug into smaller one:

    pour 14 water from bigger jug into the smaller jug until full -> 10 left in the bigger jug
    pour 10 water from bigger jug into the smaller jug until full -> 6 left in the bigger jug
    pour 6 water from bigger jug into the smaller jug until full -> 2 left in the bigger jug (let's pour this 2 into the smaller one)
    pour 14 water from bigger jug into the smaller jug until full -> 12 left in the bigger jug
    pour 12 water from bigger jug into the smaller jug until full -> 8 left in the bigger jug
    pour 8 water from bigger jug into the smaller jug until full -> 4 left in the bigger jug

    This is the second time we see 4, so we should stop. So we have:

    4 14: 10 6 2 12 8 4
    

    Similarly:

    5 17: 12 7 2 14 9 4 16 11 6 1 13 8 3 15 10 5
    5 16: 11 6 1 12 7 2 13 8 3 14 9 4 15 10 5
    

    A java implementing here:

    public class Solution {
        public boolean canMeasureWater(int x, int y, int z) {e
            int l = Math.min(x,y), h = Math.max(x,y);
            int d = h - l;
            
            // some special cases
            if (z == 0) return true;
            if (z > x + y) return false; // big z
            if (l == 0) return h == z;
            if (d == 0) return z == x || z == x + y; // same jug
            if (x == z || y == z || x + y == z) return true;
            
            int cur;
            if (d < l) { // similar jugs
                if (d == z || d + x == z || d + y == z) return true;
                cur = l - d;
                while (cur != d) {
                    if (cur == z || cur + x == z || cur + y == z) return true;
                    if (cur < d) {
                        cur = l - (h - cur - l);
                    } else {
                        cur -= d;
                    }
                }
            } else { // one big one small
                cur = h - l;
                while (cur != l) {
                    if (cur == z || cur + l == z) return true;
                    if (cur < l) {
                        cur = h - (l - cur);
                    } else {
                        cur -= l;
                    }
                }
            }
            return false;
        }
    }
    

    It's kind of interesting, but I guess we are still better off with the short GCD solution in an interview - maybe Microsoft just wanted to ask how to find GCD :P


Log in to reply
 

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