Measuring Water with Two Cups: Logical Analysis and C++ Implementation

Today we examine a popular Tencent interview question: given two cups A (9 L) and B (15 L) with unlimited water, determine whether a desired amount n liters can be measured and, if possible, output the steps.

Logical analysis : By repeatedly filling, pouring, and emptying the cups we effectively perform the Euclidean algorithm, so the measurable volumes are exactly multiples of gcd(A, B). For A = 9 and B = 15, gcd(9,15)=3, thus any volume that is a multiple of 3 L (0, 3, 6, 9, 12, 15, 18…) can be obtained.

The following C++ functions implement the test:

#include <iostream>
using namespace std;

int gcd(int x, int y) {
    int z = y;
    while (x % y != 0) {
        z = x % y;
        x = y;
        y = z;
    }
    return z;
}

bool can(int A, int B, int n) {
    if (n % gcd(A, B) == 0) {
        return true;
    }
    return false;
}

int main() {
    for (int n = 0; n < 20; n++) // test
    {
        if (can(9, 15, n)) {
            cout << n << endl;
        }
    }
    return 0;
}

Running this program prints the reachable volumes: 0, 3, 6, 9, 12, 15, 18.

Constructing the pouring steps : Once a target n (multiple of 3) is chosen, we can simulate the process. The following C++ routine performs the actual pouring operations and prints each action.

#include <iostream>
using namespace std;

void pour(int A, int B, int target) {
    // inA, inB represent current water amounts in cups A and B
    int inA = 0;
    int inB = 0;
    int flag = 0;
    while (1) {
        // safety guard
        if (flag++ > 999) {
            cout << "Fail" << endl;
            break;
        }
        if (0 == inA) {
            cout << "fill A" << endl;
            inA = A;
        } else {
            cout << "pour A into B" << endl;
            inB += inA;
            if (inB >= B) {
                inA = inB - B;
                cout << "empty B" << endl;
                inB = 0;
            } else {
                inA = 0;
            }
        }
        if (target == inA || target == inB) {
            cout << "Success, OK!" << endl;
            break;
        }
    }
}

int main() {
    int A = 9;
    int B = 15;
    int n = 6; // example target
    // proven that any A, B, n can be reduced to 0 <= n < A < B
    pour(A, B, n);
    return 0;
}

For the example target 6 L the program outputs the sequence:

fill A
pour A into B
fill A
pour A into B
empty B
pour A into B
fill A
pour A into B
fill A
pour A into B
empty B
Success, OK!

The key to solving the problem lies in the logical analysis (gcd reasoning); the coding part follows naturally once the feasibility condition is known.

Hope this explanation helps you tackle similar interview puzzles.