Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream
1. The subject
There are two kettles with capacities of XXX and YYy litres and an infinite amount of water. Can you use these two kettles to get exactly ZZZ litres of water? If you can, use one or two of the above jugs to hold ZZZ litres of water.
Are you allowed to:
- Fill any jug
- Empty any water bottle
- Pour water from one kettle to another until it is full or empty
Example 1: Input x = 3, y = 5, z = 4 Output: True Example 2: input x = 2, y = 6, z = 5 Output: FalseCopy the code2.
2.1 Depth-first search/backtracking
First, the problem is modeled. Looking at the problem, you can see that at any given moment, the state of the problem can be determined by two numbers: the amount of water in pot X, and the amount of water in pot Y.
At any given moment, we can and only can do the following:
- Fill pot X with water until pot Y is full or empty;
- Fill pot X with water from pot Y until it is full or empty;
- Fill up pot X;
- Fill the pot with Y;
- Empty pot X;
- Empty the Y pot. Therefore, this problem can be solved using depth-first search. Each step in the search has remain_x, remain_y as status, which is the amount of water in POTS X and Y. At each step of the search, we try all the operations in turn, recursively searching down. This could lead us into endless recursion, so we also need to use a HashSet to store all of the searched remain_X, Remain_Y states, guaranteeing that each state is searched at most once
using PII = pair<int.int>;
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
stack<PII> stk;
stk.emplace(0.0);
auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second); };unordered_set<PII, decltype(hash_function)> seen(0, hash_function);
while(! stk.empty()) {
if (seen.count(stk.top())) {
stk.pop(a);continue;
}
seen.emplace(stk.top());
auto [remain_x, remain_y] = stk.top(a); stk.pop(a);if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
return true;
}
// Fill up the pot.
stk.emplace(x, remain_y);
// Fill the Y pot.
stk.emplace(remain_x, y);
// Empty the pot.
stk.emplace(0, remain_y);
// Empty the Y pot.
stk.emplace(remain_x, 0);
// Pour the water from pot X into pot Y until it is full or empty.
stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));
// Fill pot X with water from pot Y until it is full or empty.
stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));
}
return false; }};Copy the codeComplexity analysis
- Time complexity: O (xy) O (xy) O (x, y), the state has the maximum number of (x + 1) (y + 1) (x + 1) (y + 1) (x + 1) (y + 1), in each state for depth first search time complexity is O (1) O (1) O (1), so the total time complexity is O (xy) O (xy) O (xy).
- Space complexity: O (xy) O (xy) O (xy), because the state has the maximum number of (x + 1) (y + 1) (x + 1) (y + 1) (x + 1) (y + 1), hash set the most benefit of (x + 1) (y + 1) (x + 1) (y + 1) (x + 1) (y + 1), So the space is O(xy)O(xy)O(xy).
2.2 Mathematical method — Bezou’s theorem
We know that each operation will only increase the amount of water in the bucket by XXX, increase YYy, decrease XXX, or decrease YYY.
You might think there’s something wrong with this: What about pouring water into a disgruntled bucket, or emptying it? Isn’t the change in XXX or YYy? Let’s explain this:
First of all, it should be clear that under the operation given in the problem, two buckets cannot be filled with water at the same time. Because looking at the operations in all the problems, the result of the operations is that at least one bucket is empty or full;
Second, there is no point in adding water to a dissatisfied bucket. Because if the other bucket is empty, the result of this operation is equivalent to filling the bucket directly from the original state; If the other bucket is full, the result is equivalent to filling both buckets from their original state.
Third, there is no point in emptying a dissatisfied bucket. Because if the other bucket is empty, the result of this operation is equivalent to returning to the original state; If the other bucket is full, this operation is equivalent to filling the other bucket from the original state.
Therefore, we can assume that each operation will only bring XXX or YYY change in the total amount of water. So our goal can be rewritten as: find a pair of integers A,ba, ba,b such that Ax +by=zax+by=zax+by=z, and as long as z≤x+yz≤x+yz≤x+ yz≤x+y, and such a,ba, ba,b exists, then our goal is achievable. This is because: if a≥0,b≥ 0A ≥0, B ≥ 0A ≥0,b≥0, then obviously the goal can be achieved. The derivation is as follows:
If a< 0A < 0A <0, you can perform the following operations:
- Pour water into pot Y;
- Pour the water from pot Y into pot X;
- If pot Y is not empty, then pot X must be full. Empty pot X, and then pour the water from pot Y into pot X.
- Repeat the above operation until a certain step, pot X is emptied for a time, and pot Y is poured for B times.
If b<0b<0b<0, the method is the same as above, x and yx are interchanged with yx and y. See the following figure for specific operations:
And Bezou’s theorem tells us that Ax plus by is equal to zax plus by is equal to zax plus by is equal to z has a solution if and only if ZZZ is a multiple of the greatest common divisor of x,yx, yx,y. So we just need to find the greatest common divisor of x,yx, yx,y and determine whether ZZZ is a multiple of it.
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % gcd(x, y) == 0; }};Copy the codeMicrosoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream