online advertising

Monday, June 27, 2016

LeetCode OJ - Water and Jug Problem

Problem:

Please find the problem here.

Analysis:

The key to this problem is number theory. Consider the following sum

$ ax + by = z $ for $ a,b \in \mathbf{Z} $

We can express $ x $ and $ y $ by multiple of there GCD $ d $, so we have

$ apd + bqd = (ap + bq)d = z $ for $ a,b,p,q \in \mathbf{Z} $, so we conclude $ z $ has to be an integer (could be 0) multiple of $ d $.

Next, we know the total jug volume is $ x + y $, so if $ z > x + y $, there is no way we can achieve $ z $.

The remaining is the interesting part. We claim that for all $ k \in [0, p+q] $, $ z = kd $ is achievable.

Without loss of generality, we assume $ a > b $ .Consider the pouring strategy as follow:

  1. Fill b
  2. Pour to a until it is full
  3. If a is full, empty it, pour any remainder to a
  4. Go back to 1
The strategy is depicted in the diagram below:

Consider $ a = 6 $, $ b = 4 $, we have reached from (0, 0) to (0, 4) by step 1, then we reach (4, 0) by step 2, step 3 is skipped, then we reach (4, 4) by step 1, (6, 2) by step 2, (2,0) by step 3, and so on ...

The strategy essentially produce us, at the end of step 3 (skipped or not), $ kb (\mod a) $. As per elementary number theory, we know these numbers will run through all the multiple of $ d $ at most $ a $, so we have proved that $ kd $ is achievable for all $ k \in [0, p] $.

But how about large multiple? For large multiple we would first achieve $ kd - b $, in that case it must be a small multiple, then we just fill the jug b to achieve it.

Solution:

The analysis above shown a pretty simple criterion what is achievable. Writing the code to check that is relatively easy. Care is taken to make sure we deal with 0 correctly.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/water-and-jug-problem/

#include "LEET_WATER_AND_JUG_PROBLEM.h"
#include <map>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <string>

using namespace std;

namespace _LEET_WATER_AND_JUG_PROBLEM
{
    class Solution
    {
    public:
        int gcd(int x, int y)
        {
            if (y > x)
            {
                return gcd(y, x);
            } 
            else if (y == 0)
            {
                return x;
            }
            else
            {
                return gcd(y, x % y);
            }
        }
        bool canMeasureWater(int x, int y, int z)
        {
            if (x == 0)
            {
                return z == 0 || z == y;
            } 
            else if (y == 0)
            {
                return z == 0 || z == x;
            }
            else if (z > x + y)
            {
                return false;
            }
            else
            {
                return (z % gcd(x, y)) == 0;
            }
        }
    };
};

using namespace _LEET_WATER_AND_JUG_PROBLEM;

int LEET_WATER_AND_JUG_PROBLEM()
{
    Solution solution;
    cout << solution.canMeasureWater(104579, 104593, 12444) << endl;
    return 0;
}

No comments :

Post a Comment