Water and Jug Problem - Practice Coding Problems

Water and Jug Problem - Problem

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:

Fill either jug completely with water
Completely empty either jug
Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty

Determine if you can measure exactly target liters using these operations.

Input & Output

Example 1 — Achievable Target

$ Input: x = 3, y = 5, target = 4

› Output: true

💡 Note: Fill 5-liter jug, pour into 3-liter jug (2 liters remain in 5-liter jug). Empty 3-liter jug, pour the 2 liters from 5-liter jug into 3-liter jug. Fill 5-liter jug again, pour 1 liter into 3-liter jug (which had 2 liters). Now 5-liter jug has 4 liters.

Example 2 — Impossible Target

$ Input: x = 2, y = 6, target = 5

› Output: false

💡 Note: GCD(2,6) = 2. Since 5 is not divisible by 2, it's impossible to measure exactly 5 liters using 2L and 6L jugs.

Example 3 — Edge Case Zero

$ Input: x = 1, y = 2, target = 0

› Output: true

💡 Note: We can always achieve 0 liters by keeping both jugs empty.

Constraints

1 ≤ x, y ≤ 10⁶
0 ≤ target ≤ x + y

Visualization

Tap to expand

Understanding the Visualization

Input

Two jug capacities (x, y) and target amount

Process

Check mathematical feasibility using GCD

Output

Boolean indicating if target is achievable

Key Takeaway

🎯 Key Insight: The problem reduces to checking if target is divisible by GCD(x,y) - a pure mathematical solution

Asked in

M Microsoft 15 G Google 12 a Amazon 8

The key insight is that this is a mathematical problem solvable using number theory. You can measure exactly target liters if and only if target is divisible by GCD(x,y) and target ≤ max(x,y). The optimal approach uses the mathematical property in O(log min(x,y)) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical GCD Solution	O(log min(x, y))	O(1)	Use mathematical properties to solve in constant time
BFS State Exploration	O(x × y)	O(x × y)	Explore all possible jug states using breadth-first search

Mathematical GCD Solution — Algorithm Steps

Calculate GCD of x and y
Check if target is divisible by GCD
Check if target ≤ max(x,y)
Return result

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate GCD

Find GCD(x,y) using Euclidean algorithm

Check Divisibility

Target must be divisible by GCD

Verify Bounds

Target must not exceed max capacity

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

bool solution(int x, int y, int target) {
    if (target == 0) return true;
    if (target > (x > y ? x : y)) return false;
    
    int gcdVal = gcd(x, y);
    return target % gcdVal == 0;
}

int main() {
    int x, y, target;
    scanf("%d", &x);
    scanf("%d", &y);
    scanf("%d", &target);
    
    bool result = solution(x, y, target);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log min(x, y))

GCD calculation using Euclidean algorithm takes logarithmic time

⚡ Linearithmic

Space Complexity

O(1)

Only uses a constant amount of extra variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical GCD Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler