LC-0365 Medium LeetCode

365. Water and Jug Problem

Math Depth-First Search Breadth-First Search

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Math, Depth-First Search, Breadth-First Search

Reading material

Math & Geometry 12 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(logn),  n is the max of (x, y)
# Space: O(1)

class Solution(object):
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a

        # The problem is to solve:
        # - check z <= x + y
        # - check if there is any (a, b) integers s.t. ax + by = z
        return z == 0 or ((z <= x + y) and (z % gcd(x, y) == 0))

Solution from kamyu104/LeetCode-Solutions · MIT