Solution: Water and Jug Problem
Understand how to solve the Water and Jug problem by applying Bézout's Identity and greatest common divisor (GCD) concepts. Learn to check if a target liter value is achievable with two jugs through simple mathematical conditions, avoiding complex simulations. This lesson helps you improve your problem-solving efficiency and grasp number theory applications in coding interviews.
We'll cover the following...
Statement
You are given two jugs with capacities of x liters and y liters, respectively, along with an infinite water supply. Determine whether it is possible for the total amount of water in both jugs may reach target liters.
You may perform the following operations any number of times:
Fill either jug completely with water.
Empty either jug completely.
Pour water from one jug into the other until either the receiving jug becomes ...