1518. Water Bottles

Time: O(log n)

Space: O(1)

Approach

Simulate; repeatedly exchange full bottles for new ones, tracking the total drunk.

Key Techniques

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Simulation

Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.

1518.cs

// Approach: Simulate; repeatedly exchange full bottles for new ones, tracking the total drunk.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int NumWaterBottles(int numBottles, int numExchange)
    {
        int ans = numBottles;

        while (numBottles >= numExchange)
        {
            numBottles -= numExchange;
            ans++;
            numBottles += 1;
        }

        return ans;
    }
}

1518.py

Python

class Solution(object):
    def numWaterBottles(self, numBottles, numExchange):
        """
        :type numBottles: int
        :type numExchange: int
        :rtype: int
        """

        ans = numBottles

        while numBottles >= numExchange:
            numBottles -= numExchange
            ans += 1
            numBottles += 1

        return ans

Was this solution helpful?