In this post we will solve LeetCode 1518. Water Bottles problem using the Java programming language.
There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink. Constraints: o 1 <= numBottles <= 100 o 2 <= numExchange <= 100 Related Topics: o Math o Simulation
Before you start solving a problem associated with a website make sure you read the current description directly from the site in order to get the current description of the problem. On occasions descriptions may be updated providing additional information that may help you come up with a better solution faster.
In this problem we start with a number of full bottles of water. The actual contents of the bottles do not matter. We are able to exchange a number of empty bottles for full ones. Using such information the function of interest needs to compute and return the total number of bottles drank.
The two suggested approaches are using math or simulation. I decided to use a simulation approach.
public int numWaterBottles(int numBottles, int numExchange) {
}
The signature for the function of interest takes as arguments the initial number of full bottles and the number of empty bottles taken in exchange for one full bottle. The function returns the total number of bottles drank.
As always I like to use my Windows computer and the VSCode IDE to solve the problem in Java. In a week or so I will be adding implementations using C++20. In addition I like to keep around a test scaffold so I can easily and offline experiment with the code. For this reason I will need to develop some test code. That said; it is simpler and faster to develop a solution using the online IDE provided by LeetCode. Note that the test code IS NOT PART OF THE SOLUTION!
9 3 main <<< numBottles: 9 main <<< numExchange: 3 <<< drank: 9 <<< exchanged: 3 <<< empty: 0 <<< drank: 12 <<< numBottles: 3 <<< exchanged: 1 <<< empty: 0 <<< drank: 13 <<< numBottles: 1 main <<< 13 15 4 main <<< numBottles: 15 main <<< numExchange: 4 <<< drank: 15 <<< exchanged: 3 <<< empty: 3 <<< drank: 18 <<< numBottles: 6 <<< exchanged: 1 <<< empty: 2 <<< drank: 19 <<< numBottles: 3 main <<< 19 1 2 main <<< numBottles: 1 main <<< numExchange: 2 main <<< 1
The test cases are separated by two blank lines.
Each test code starts with two input lines. The first holds the initial number of full bottles and the second the number of empty bottles that may be exchanged for one full bottle.
Our test code seems to read in the two input lines and assign the values to the respective variables which will be used as arguments to the function of interest. The values of the variables are then displayed to verify that all is well before calling the function of interest.
As I am generating this post I noticed that the value of the result is displayed with no label. In addition we are calling a single implementation of the function of interest. As we will see shortly, there are two implementations of the function of interest. One is a simplification of the other but both contain the same operations. Sorry about that!
The values that follow are displayed by the implementation of the function of interest. They help us follow the algorithm.
The result is in the last line of each test case.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read numBottles ****
int numBottles = Integer.parseInt(br.readLine().trim());
// **** read numExchange ****
int numExchange = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< numBottles: " + numBottles);
System.out.println("main <<< numExchange: " + numExchange);
// ***** call function of interest and display result ****
System.out.println("main <<< numWaterBottles0: " + numWaterBottles0(numBottles, numExchange));
// ***** call function of interest and display result ****
System.out.println("main <<< numWaterBottles: " + numWaterBottles(numBottles, numExchange));
}
The test code opens a buffered reader, reads the two input lines, closes the buffered reader, displays the contents of the variables which will be used as arguments for the two implementations of the function of interest. The functions are called and the results displayed. Please note that the test code IS NOT PART OF THE SOLUTION.
/**
* Given the two integers numBottles and numExchange,
* return the maximum number of water bottles you can drink.
*
* Simulation.
*
* Execution: O(n / m) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.7 MB, less than 9.28% of Java online submissions.
*
* 64 / 64 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 37.7 MB
*/
static public int numWaterBottles(int numBottles, int numExchange) {
// **** sanity checks ****
if (numBottles < numExchange) return numBottles;
// **** initialization ****
int drank = numBottles;
// **** loop until we are not able to exchange bottles ****
while (numBottles >= numExchange) {
// **** compute number of bottles exchanged ****
int exchanged = numBottles / numExchange;
// ???? ????
System.out.println("<<< exchanged: " + exchanged);
// **** compute number of empty bottles ****
int empty = numBottles % numExchange;
// ???? ????
System.out.println("<<< empty: " + empty);
// **** update number of bottles drank ****
drank += exchanged;
// ???? ????
System.out.println("<<< drank: " + drank);
// **** update numBottles ****
numBottles = empty + exchanged;
// ???? ????
System.out.println("<<< numBottles: " + numBottles);
}
// **** return number of bottles drank ****
return drank;
}
We will use a simulation approach.
We start by performing some sanity checks. The initialization steps follow. One way or the other we will be able to drink all the full bottles we start with.
We enter a while loop. The condition that will allow us to get and drink more bottles of water states that as long as we have empty bottles to exchange, we will exchange them for more full bottles.
Inside the loop we perform some computations. I believe the comments are good enough to allow us to follow what the simulation is doing.
After we exit the loop the function of interest returns the total number of bottles of water we drank.
Please take a look at the comments section of this function. It seems we did a decent job with the approach and implementation. I call your attention to the memory used. We should compare it with the values returned by the second implementation of the function of interest.
/**
* Given the two integers numBottles and numExchange,
* return the maximum number of water bottles you can drink.
*
* Simulation.
*
* Execution: O(n / m) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.9 MB, less than 5.77% of Java online submissions.
*
* 64 / 64 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 37.9 MB
*/
static public int numWaterBottles0(int numBottles, int numExchange) {
// **** sanity checks ****
if (numBottles < numExchange) return numBottles;
// **** initialization ****
int drank = numBottles;
// **** loop until we are not able to exchange bottles ****
while (numBottles >= numExchange) {
// **** update number of bottles drunk ****
drank += numBottles / numExchange;
// **** update number of bottles ****
numBottles = (numBottles / numExchange) + (numBottles % numExchange);
}
// **** return number of bottles drank ****
return drank;
}
This implementation uses the same approach. The difference is that the code is simpler and shorter. At this time I do not have much to add.
Please take a look at the comments section. In particular the memory usage. It seems that it is slightly worse than the previous implementation. Of course it might be due to the load at the LeetCode website while I submitted the code multiple times to see if this implementation would reduce the space. It did not.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named WaterBottles.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John