1518. Water Bottles

Intuition

The problem involves determining the maximum number of water bottles you can drink given an initial number of full water bottles a and the number of empty bottles x required to exchange for one full bottle. The solution can be derived using the concept of the sum of an infinite geometric progression.

Approach: Math

Explanation:

1. Understanding the Problem:
2. You start with a full water bottles.
3. For every x empty bottles, you can exchange them for 1 full bottle.
4. Each time you drink a bottle, it becomes an empty bottle which can potentially be exchanged for another full bottle.
5. Modeling the Problem as a Geometric Progression:
6. Every time you drink a bottle, it contributes to the total number of full bottles you can eventually drink.
7. Let's denote:
   • a as the initial number of full bottles.
   • x as the exchange rate (number of empty bottles needed to get 1 full bottle).
8. Summing the Bottles:
9. After drinking the initial a bottles, you get a empty bottles.
10. These a empty bottles can be exchanged for a/x full bottles.
11. Those a/x full bottles will eventually also become empty and can be exchanged further, forming an infinite sequence.
12. Using the Sum of an Infinite Geometric Progression:
13. The sum S of an infinite geometric series where the first term is a and the common ratio r is 1/x is given by:

    • S = a/1 - r

14. In this case, the first term a is the initial number of full bottles, and the common ratio r is 1/x.
15. Formula Derivation:
16. Substitute r = 1/x into the geometric series formula:

    • S = a/1 - frac1x = a/fracx-1x = a · x/x - 1

17. However, since we are dealing with integer bottles, we adjust the formula to account for integer division:

    • S = a · x - 1/x - 1

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Code

class Solution {
public:
    int numWaterBottles(int a, int x) {
        return (a * x - 1) / (x - 1);
    }
};