LeetCode Entry

1518. Water Bottles

7.07.2024 easy 2024 kotlin rust

Bottles drink and exchange simulation

1518. Water Bottles easy blog post substack youtube 2024-07-07_09-25_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/662

Problem TLDR

Bottles drink and exchange simulation #easy #math #simulation

Intuition

Run the simulation:


    // a n
    // drink                      empty
    // a                          a
    // a/n                        a/n+a%n
    // (a/n+a%n)/n                (a/n+a%n)/n+(a/n+a%n)%n

There is also a math solution based on geometric series sum \(a + a/n + a/n^2 + ... = a/(1-1/n) = an/(n-1)\) (https://en.wikipedia.org/wiki/Geometric_series). Given that, it is sometimes off by one, we can write \((an - 1)/(n - 1)\). I doubt I could remember this in an interview or a contest though.

Approach

Let’s use as little variables as possible.

Complexity

  • Time complexity: \(O(log_e(b))\), e - numExchange, b - numBottles

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

Code


    fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
        var drink = numBottles
        var empty = numBottles
        while (empty >= numExchange) {
            drink += empty / numExchange
            empty = empty / numExchange + empty % numExchange
        }
        return drink
    }



    pub fn num_water_bottles(num_bottles: i32, num_exchange: i32) -> i32 {
        let (mut drink, mut empty) = (num_bottles, num_bottles);
        while empty >= num_exchange {
            drink += empty / num_exchange;
            empty = empty / num_exchange + empty % num_exchange
        }
        drink
    }