# 365. Water and Jug Problem

The problem's detailed definition is not included in this article; however, it's available in the following link:
https://leetcode.com/problems/water-and-jug-problem/description

To solve this problem, we introduce two approaches. The first one is *induction approach*, and the second one relys on *mathematical approach* to find an *analytical solution*.

# 1. Induction Approach

## Intuition


Let $a$ and $b$ denote the capacities of jug1 and jug2, respectively. The variable $x$ represents the total volume of water in the jugs, while $t$ indicates the target capacity. Without loss of generality, we assume that jug1 (i.e.,$a$) has a greater capacity than jug2 (i.e.,$b$). Moreover, the term *measurable by $x$* in this article is interpreted as that $x$ can be measured by using these jugs through a series of available operations:

1. Fill any of the jugs with water.
2. Empty any of the jugs.
3. Pour water from one jug into another till the other jug is completely full, or the first jug itself is empty.

Initially, we commence with a measurable state where the volume is $0$. Subsequently, in each induction step, we assume that $x$ can be achieved through a sequence of operations from the initial measurable state of $0$. This imply that $x$ is measurable. We then investigate the measurable outcomes, denoted as $x'$, resulting from the application of operations to $x$. Our objective is to determine the existence of an $x'$ such that $t=x'$.


<!--This can be solved by dynamic approach since different sequence of operations may produce the same outcome. For example, if jug1 and jug2 are all empty initially, conducting the sequences of operations of **fill jug1** and then immediately **empty jug1** will always comes to the same result. Hence, we can design the subproblems in dynamic programming as reaching a certain volumes after applying sequence of operations.-->

When limited to operations 1 and 2, our achievable outcomes are restricted to $0$, $a$, $b$, and $a+b$. To expand our outcome possibilities, the inclusion of operation 3 becomes necessary.

However, a single execution of operation 3 doesn’t alter the total volume of water. To generate new measurable values, a sequence of operations--*operation 3 followed by operation 1* or *operation 3 followed by operation 2*--is required. To indicate the jug involved in operations 1 and 2 after operation 3, we utilize the notations *3->2a*, *3->2b*, *3->1a*, *and 3->1b*. These operations are visually represented below:


<!--
Based on the above observations, if we start from two empty jugs, a valid $x'$ after repeatedly applying 3->1 or 3->2, at least one of these jugs must be empty or full(i.e., we could not have both jugs non-empty and non-full).
-->

## Approach
<!-- Describe your approach to solving the problem. -->
<!--

-->

To begin, let's explore the potential values of $x'$ when $x < a$.

Given that $a > b$, we utilize op3 to transfer all the water into jug1. Subsequently, for the following discussions, we assume that jug2 is empty. To derive a new measurable value of $x'$ using the available operations, we need to consider the following three conditions:

<!--In the followings, we need to show that when $x \geq a$, applying operation 3->1 or 3->2 won't generate $x'$ such that $a\leq x' < a+b$. If it is true, we only need to recursively solve the subproblem of $x < a$ and check whether $t$ is measurable by checking whether $x=t$, $x+a=t$ or $x+b=t$.-->

1. $a - x \geq b$
In this scenario, jug1 has ample empty space to accommodate the volume of water in jug2. Employing op1b fills jug2, after which op3 transfers its contents to jug1. The resulting outcome is given by $$x'=x+b.$$
This method allows for the repetition of op1 and op3 if $a-x' > b$, meaning $a-(x+b) > b$, until $a-(x+nb) < b$ is achieved.

2. $a - x < b$
If jug1 lacks sufficient space to accommodate b, we can still utilize the remaining capacity, $a-x$, to create a new value. Initially, we employ op1b to fill jug2 and subsequently use op3 to transfer its contents into jug1 until jug1 reaches its capacity. Then, employing op2a, we empty jug1, resulting in a new value for the remaining water in jug2:
$$x' = b-(a-x).$$
Notice that to enable the application of the induction approach to $x'$, we must use op3 to transfer the water back to jug1.
3. $x < b$
In this scenario, we can transfer the water into jug2 and utilize the available empty space in jug2 (i.e., $a-x$) to create a new value. Here are the steps: begin by moving the water into jug2 using op3, then fill jug1 using op1a, fill the water to jug2 from jug1 with op3, and finally empty jug2 using op2b. This sequence results in: $$x'=a-(b-x).$$

Note that only conditions 1 and 2 are mutually exclusive. However, conditions 3 and 2, as well as conditions 3 and 1, can be fulfilled simultaneously. Consequently, a single value of $x$ could yield multiple values of $x'$. To manage this situation, we utilize a queue, denoted as q, to store these values.

In cases where $x' > a$, it can be proved that the values are limited to $x+a$ or $x+b$, provided that $x<a$. The detailed is omitted in this article. Consequently, we solely verify whether $x+a=t$ or $x+b=t$ without requiring inductive steps for $x' > a$. The implementation is illustrated below.


<!--

If $x \geq a$, applying operation 3, there is no empty jugs, and one of the jug must be full. Hence, applying operation 3->1 will only generate $x' = a+b$. When $x\geq a$, applying operation 3->2 will generate $x \leq a$ since $x \leq a+b$.

Then, we consider the boundary case, $x=a$, then applying operation 3->2 can only generate $x'=a-b < a$. It is only posible to generate $x'=a$ when applying 3->2b to $x=a+b$. The state transitions of $x$ applying operations can be shown below:

-->

## Code

class Solution:
    def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
    
        # Define a,b,t and ensure a > b.
        a = max(jug1Capacity,jug2Capacity)
        b = min(jug1Capacity,jug2Capacity)
        t = targetCapacity
        
        # the queue for store x', and initial value of x is 0 .
        q = [0]
        
        # cache sto store known outcome, to avoid repeated calculation.
        cache = set()

        # trivial case
        if t > a + b:
            return False

        # induction steps
        while len(q) > 0:
            
            x = q.pop()
                    
            # If x has been calculated, we don't need to do it again.
            if x in cache:
                continue

            # to denote that x is calculated
            cache.add(x)

            #to check whether t is measurable, we need to .
            if x == t or x+a == t or x+b == t:
                return True
            
            # three condition for induction, i.e., to generate new x'.
            if a-x >= b:
                # op1b->3
                q.append(x+b)
            elif a-x < b:
                # op1b->3->2a->3
                q.append(b-(a-x))
            if x < b:
                # op3->1a->3->2b
                q.append(a-(b-x))  
                
        # t could not be measured by jug1 and jug2
        return False

The runtime and memory are:


# 2. Analytical Approach

## Intuition
As $x$ is derived through a sequence of linear combinations of $b$ and $a-b$ starting from $0$, we can formulate the possible values of $x$ and analytically determine if there exists an $x$ such that $t=x$.

To be more precise, $x$ is obrained from
$$
x \leftarrow \begin{cases}
x+b & \text{if $a-x \geq b$},\\
b-(a-x) & \text{if $a-x < b$},\\
a-(b-x) & \text{if $x < b$},
\end{cases}
$$
and then we check whether $t=x$, $t=x+a$ or $t=x+b$.

Hence, this problem can be formulated as:

$$
t = A(x+b) + B\left(b-(a-x)\right) + C\left(a-(b-x)\right) + D(x+a) + E(x+b),
$$
subject to
$$
\begin{cases}
A \geq 0, \\
B \geq 0, \\
C \geq 0, \\
1 \geq D \geq 0, \\
1 \geq E \geq 0, \\
\text{$A$, $B$, $C$, $D$ and $E$ are integers.}
\end{cases}
$$

where $A$, $B$, and $C$ denote the counts of applying $x+b$, $b-(a-x)$, and $a-(b-x)$, respectively, to derive the final value of $x$. Meanwhile, $D$ and $E$ determine whether $t=x+a$ or $t=x+b$.

## Approach

Given the initial state $x=0$, through appropriate arrangement of the equation involving $t$, we obtain:

$$
\begin{aligned}
&t = A(x+b) + B(b-(a-0)) + C(a-(b-0)) + D(0+a) + E(0+b) \\
&\Rightarrow t = Ab + B(-(a-b)) + C(a-b) + Da + Eb \\
&\Rightarrow t = (C-B) (a-b) + (A+E)b + Da \\
&\Rightarrow t = (C-B) (a-b) + (A+E)b + D(a-b) + Db \\
&\Rightarrow t = (C-B+D)(a-b) + (A+E+D)b. \\
\end{aligned}
$$

Defining $\alpha=C-B+D$ and $\beta=A+E+D$, the problem becomes finding an integer solution for $(\alpha,\beta)$ in the following equation:
$$
t = \alpha(a-b) + \beta b,
$$
subject to
$$
\begin{cases}
\beta \geq 0, \\
\text{$\alpha$ and $\beta$ are integers.}
\end{cases}
$$

To ascertain a valid solution, it's crucial to verify whether $t$ is divisible by the greatest common divisor of $a-b$ and $b$. Should a valid solution exist, there are infinitely many such solutions due to the positivity of $a-b$ and $b$, resulting in an infinite number of solutions within the $\beta\geq 0$ half-plane.

In cases where there's no integer solution, implying a lack of a valid solution, $t$ is deemed non-measurable.

The implementation is straightforward and succinct, outlined below.

## Code

class Solution:
    def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
        # initialize
        a = max(jug1Capacity,jug2Capacity)
        b = min(jug1Capacity,jug2Capacity)
        t = targetCapacity
        
        # trivial cases
        if a == b:
            return t in [0,a,2*a]
        elif t > a+b:
            return False
        
        # Check whether t can be devided by the gcd of a-b and b.
        else:
            return t % math.gcd(a,b) == 0                

The execution time is tenfold quicker compared to the prior method, and the code is significantly more concise.