Teaching Kids Programming – Beer Bottle Exchange Algorithm via Simulation

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer n representing n full beer bottles. Given that you can exchange 3 empty beer bottles for 1 full beer bottle, return the number of beer bottles you can drink.

Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 9
Output
13
Explanation
In first round, we drink 9 beer bottles.
We can exchange the 9 empty ones for 3 beer bottles.
We can exchange the 3 empty ones for 1 beer bottle.

Beer Bottle Exchange Algorithm via Simulation

While there are more than 3 bottles, we can keep exchanging empty bottles with beers. We can simulate this process until there are less than 3 bottles. We have to add up the remaining bottles during the exchanging process.

class Solution:
    def solve(self, n):
        ans = n
        while n >= 3:
            exchange = n // 3
            ans += exchange
            n = (n % 3) + exchange
        return ans

The time complexity is .

–EOF (The Ultimate Computing & Technology Blog) —