LeetCode 1518. Water Bottles Java Solution

Problem Description

• Problem: LeetCode 1518. Water Bottles

• Description: We have numBottles water bottles. We can exchange numExchange empty bottles for one new full water bottle. The goal is to calculate the maximum number of water bottles we can drink.

Approach

Idea:

• Initially, we drink all numBottles water bottles.

• After drinking, we have numBottles empty bottles.

• We exchange the empty bottles for new full bottles as much as possible. We drink these new bottles and repeat the process until we can't exchange anymore.

• We repeat this process until the number of empty bottles is less than numExchange.

• Finally, we return the total number of water bottles we can drink.

Algorithm:

1. Initialize canDrink with the initial number of water bottles.

2. While numBottles is greater than or equal to numExchange:

   1. Calculate the number of new bottles obtained by dividing numBottles by numExchange. (numBottles / numExchange)

   2. As newBottles is of type int, any fractional part is discarded.

   3. Calculate the remaining empty bottles after exchanging, which is numBottles modulo numExchange. (numBottles % numExchange)

   4. Add the number of new bottles to canDrink.

   5. Update numBottles to the sum of the new bottles obtained and the remaining empty bottles.

3. After the loop ends, return the value of canDrink.

Code

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int canDrink = numBottles;

        while(numBottles >= numExchange){
            int newBottles = numBottles / numExchange;
            canDrink += newBottles;
            numBottles = newBottles + (numBottles % numExchange);
        }

        return canDrink;
    }
}

Conclusion

Time Complexity:

• The number of bottles decreases with each exchange, so the loop runs at most log(numBottles) times.

• Thus, the time complexity is O(log n).

Space Complexity:

• No additional space is used, so the space complexity is O(1).