Not math solution, stupid but accepted.


  • 2
    Y
    class Solution {
    public:
        unordered_map<int, int> canFill;
        unordered_map<int, int> depends;
        bool measure_helper_iterative(int x, int y, int z)
        {
        	int nextFill = 0;
        	while (canFill.find(z) == canFill.end())
        	{
        		z = z % x;
        		nextFill = y - x + z;
        		if (depends[nextFill] == 1)return false;
        		depends[nextFill] = 1;
        		z = nextFill;
        	}
        	return true;
        }
        bool canMeasureWater(int x, int y, int z) {
            if(z == 0)return true;
            if(x + y < z)return false;
            if(x == 0)return y == z;
            if(y == 0)return x == z;
        	if (x > y)
        	{
        		int a = x;
        		x = y;
        		y = a;
        	}
        	int i = 0;
        	while (x * i < y)
        	{
        		canFill[x * i] = 1;
        		canFill[y - x * i] = 1;
        		i++;
        	}
        	canFill[x * i - y] = 1;
        	return measure_helper_iterative(x, y, z);
        }
    };
    

    The basic idea is to simulate the process of transfer the water from one jug to the other. For example, jug x(smaller) and y(bigger). to contain amount z (valid amount), the jug x should fill full n times (imagine using jug x to fill and transfer to jug y, because jug y is bigger, so definitely can hold) and the last time, only fill z%x liters water, let's say "p = z%x". so to let the jug x only hold p liters water, you need to transfer water from jug x to jug y one or multiple times, but the last time only transfer x-p liters water, so it means jug y needs to hold y-(x-p) = y-x+p liters water so that the last time when water transfer from jug x to y can make jug full. Now the problem evolved to use jug x and y to contain y-x+p liters water. keep moving forward, z depends on y-x+p, depends on..... if the y-x+p is found in the hash map, meaning there's a circle, jug x and y will never be able to contains z liters water.


Log in to reply
 

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