Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/a43dfc2408556f63e98ba38141253a79 to your computer and use it in GitHub Desktop.
Save jianminchen/a43dfc2408556f63e98ba38141253a79 to your computer and use it in GitHub Desktop.
Leetcode365 water and Jug problem - practice 1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode365_WaterAndJugProblem
{
class Program
{
/// <summary>
/// source code from
/// https://leetcode.com/problems/water-and-jug-problem/discuss/83765/Simple-java-solution-not-using-the-math-function
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
var result = canMeasureWater(4, 6, 2);
var result2 = canMeasureWater(4, 6, 8);
var result3 = canMeasureWater(4, 6, 10);
var result4 = canMeasureWater(4, 6, 9);
}
public static bool canMeasureWater(int x, int y, int z)
{
// corner cases
if (x < 0 && y < 0)
{
return false;
}
if (z > (x + y))
{
return false;
}
if (x == z || y == z || x + y == z || z == 0)
{
return true;
}
// initialize conditions. We fill the bigger bucket full first and leave smaller one empty
int bigger = Math.Max(x, y);
int smaller = Math.Min(x, y);
int biggerBucket = bigger;
int smallerBucket = 0;
// when smaller bucket is full we have tried every sum combinations
while (smallerBucket != smaller)
{
int gap = smaller - smallerBucket;
int leftOver = biggerBucket - gap;
if (leftOver == z || leftOver + smaller == z)
{
return true;
}
if (leftOver <= smaller)
{
if (leftOver + bigger == z)
{
return true;
}
smallerBucket = leftOver;
biggerBucket = bigger;
}
else
{
smallerBucket = 0;
biggerBucket = leftOver;
}
}
return false;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment