Skip to content

3100. Water Bottles II

Description

You are given two integers numBottles and numExchange.

numBottles represents the number of full water bottles that you initially have. In one operation, you can perform one of the following operations:

  • Drink any number of full water bottles turning them into empty bottles.
  • Exchange numExchange empty bottles with one full water bottle. Then, increase numExchange by one.

Note that you cannot exchange multiple batches of empty bottles for the same value of numExchange. For example, if numBottles == 3 and numExchange == 1, you cannot exchange 3 empty water bottles for 3 full bottles.

Return the maximum number of water bottles you can drink.

 

Example 1:

Input: numBottles = 13, numExchange = 6
Output: 15
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Example 2:

Input: numBottles = 10, numExchange = 3
Output: 13
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

 

Constraints:

  • 1 <= numBottles <= 100
  • 1 <= numExchange <= 100

Solutions

Solution 1: Simulation

Thinking

Each successful exchange increments the threshold, so a closed form must track a quadratic relation between empties and the growing cost. Both \(n\) and \(\textit{numExchange}\) are at most \(100\), and a direct loop runs in \(O(\sqrt{n})\), which fits the limits.

All full bottles can be drunk first. Afterwards the only question is whether the empty count is at least the current threshold. Exchanging one bottle, drinking it, and incrementing the threshold reduces empties by \(\textit{numExchange}-1\).

Add \(\textit{numBottles}\) to the answer, then while empties are enough subtract the threshold, increment it, and add one drunk bottle. The accumulated count is the maximum number of bottles drunk.

We can drink all the full water bottles at the beginning, so initially the amount of water we drink is \(\textit{numBottles}\). Then, we repeatedly perform the following operations:

  • If we currently have \(\textit{numExchange}\) empty bottles, we can exchange them for one full bottle. After the exchange, the value of \(\textit{numExchange}\) increases by \(1\). Then, we drink this bottle, increasing the total amount of water drunk by \(1\), and the number of empty bottles increases by \(1\).
  • If we do not have \(\textit{numExchange}\) empty bottles, we cannot exchange for more water and should stop.

We repeat the above process until we can no longer exchange bottles. The total amount of water drunk is the answer.

The time complexity is \(O(\sqrt{n})\), where \(n\) is the initial number of full bottles. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        ans = numBottles
        while numBottles >= numExchange:
            numBottles -= numExchange
            numExchange += 1
            ans += 1
            numBottles += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles;
        while (numBottles >= numExchange) {
            numBottles -= numExchange;
            ++numExchange;
            ++ans;
            ++numBottles;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles;
        while (numBottles >= numExchange) {
            numBottles -= numExchange;
            ++numExchange;
            ++ans;
            ++numBottles;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maxBottlesDrunk(numBottles int, numExchange int) int {
    ans := numBottles
    for numBottles >= numExchange {
        numBottles -= numExchange
        numExchange++
        ans++
        numBottles++
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function maxBottlesDrunk(numBottles: number, numExchange: number): number {
    let ans = numBottles;
    while (numBottles >= numExchange) {
        numBottles -= numExchange;
        ++numExchange;
        ++ans;
        ++numBottles;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn max_bottles_drunk(mut num_bottles: i32, mut num_exchange: i32) -> i32 {
        let mut ans = num_bottles;

        while num_bottles >= num_exchange {
            num_bottles -= num_exchange;
            num_exchange += 1;
            ans += 1;
            num_bottles += 1;
        }

        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Solution {
    public int MaxBottlesDrunk(int numBottles, int numExchange) {
        int ans = numBottles;
        while (numBottles >= numExchange) {
            numBottles -= numExchange;
            ++numExchange;
            ++ans;
            ++numBottles;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    /**
     * @param Integer $numBottles
     * @param Integer $numExchange
     * @return Integer
     */
    function maxBottlesDrunk($numBottles, $numExchange) {
        $ans = $numBottles;
        while ($numBottles >= $numExchange) {
            $numBottles -= $numExchange;
            $numExchange++;
            $ans++;
            $numBottles++;
        }
        return $ans;
    }
}

Comments