Problem statement

https://leetcode.com/problems/water-and-jug-problem/

Solution

Mathematical problem, if we have x and y, we can create all numbers less than max(x, y) such that they divided by (x, y). To prove this however is a bit tricky.

Other possible idea how to solve it is to try to check all options, using dfs or bfs.

Complexity

Code

class Solution:
    def canMeasureWater(self, j1, j2, target):
        return target % gcd(j1, j2) == 0 and j1 + j2 >= target