365. Water and Jug Problem

Medium

30 Points

Math

Depth-First Search

Breadth-First Search

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

Examples

Example 1

Input: x = 3, y = 5, target = 4 Output: true Explanation: Follow these steps to reach a total of 4 liters: Reference: The Die Hard example.

Example 2

Input: x = 2, y = 6, target = 5 Output: false

Example 3

Input: x = 1, y = 2, target = 3 Output: true Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

Constraints

1 <= x, y, target <= 103