Problem

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

Examples

Example 1:

1
2
3
4

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Lets assume ● is filled bottle, and ○ is empty bottle. Lets denote D for drink and X for exchange, then this is how it will work.

1
2
3
4

Initial   
● ● ●         ○ ○ ○         ●         ○
● ● ●   =D=>  ○ ○ ○   =X=>  ●   =D=>  ○   =X=>  ●   =D=>  ○
● ● ●         ○ ○ ○         ●         ○

Example 2:

1
2
3
4

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.
Similar Problems

Solution

Method 1 - Iterative

As long as there are at least numExchange bottles remaining, we can drink them and exchange the empty bottles for full ones.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
  int numWaterBottles(int numBottles, int numExchange) {
    int ans = numBottles;
    while (numBottles >= numExchange) {
      int exchange = numBottles / numExchange;
      ans += exchange;
      numBottles = exchange + (numBottles % numExchange);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

func numWaterBottles(numBottles int, numExchange int) int {
  ans := numBottles
  for numBottles >= numExchange {
    exchange := numBottles / numExchange
    ans += exchange
    numBottles = exchange + (numBottles % numExchange)
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int ans = numBottles;
        while (numBottles >= numExchange) {
            int remainder = numBottles % numExchange;
            numBottles /= numExchange;
            ans += numBottles;
            numBottles += remainder;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution:
  def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
    ans = numBottles
    while numBottles >= numExchange:
      exchange = numBottles // numExchange
      ans += exchange
      numBottles = exchange + (numBottles % numExchange)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
    var bottles = numBottles
    var ans = bottles
    while (bottles >= numExchange) {
      val exchange = bottles / numExchange
      ans += exchange
      bottles = exchange + (bottles % numExchange)
    }
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
  pub fn num_water_bottles(mut num_bottles: i32, num_exchange: i32) -> i32 {
    let mut ans = num_bottles;
    while num_bottles >= num_exchange {
      let exchange = num_bottles / num_exchange;
      ans += exchange;
      num_bottles = exchange + (num_bottles % num_exchange);
    }
    ans
  }
}
1
2
3
4
5
6
7
8
9

function numWaterBottles(numBottles: number, numExchange: number): number {
  let ans = numBottles;
  while (numBottles >= numExchange) {
    const exchange = Math.floor(numBottles / numExchange);
    ans += exchange;
    numBottles = exchange + (numBottles % numExchange);
  }
  return ans;
}

Complexity

  • ⏰ Time complexity: O(log n), where n is number of bottles
  • 🧺 Space complexity: O(1)

Method 2 - Geometric Progression

We know that in Geometric Progression, when the progression is converging, then the formula is: $$ S_{\infty} = \frac{a}{1-r} $$ For eg. when r = 0.5 = 1/2, this is GP is converging.

These are the terms of GP for eg. 1:

1
2
3

t0 = 9  
t1 = 3
t2 = 1

So, we can see that a = 9, r = 1/3,

1

S = a / (1 - r) = 9 / (1 - 1/3) = 9 / 2/3 = 9 * 3 / 2 = 27 / 2 = 13

Note, answer is not 13.5, but 13, as we want 1 complete bottle, not half empty bottles.

So, this example worked, but we need to make sure we do integer division. So, lets derive the formula. Let n be initial bottles given, and k be number of bottles we exchange to get 1 full bottle. First exchange:

$$ \left\lfloor \frac{n}{k} \right\rfloor $$

Remaining Empty Bottles:

$$ n - \left( k \cdot \left\lfloor \frac{n}{k} \right\rfloor \right) $$ Number of Full Bottles After Each Exchange: $$ \sum_{i=0}^{\infty} \left\lfloor \frac{n_i}{k} \right\rfloor $$

The total number of bottles you can drink is the sum of the initial bottles and the total number of full bottles obtained through exchanges. To simplify this calculation, we use the formula:

$$ \text{Total} = n + \left\lfloor \sum_{i=0}^{\infty} \left\lfloor \frac{n}{k} \right\rfloor \right\rfloor $$

To derive the total exchanges, realize that every additional bottle obtained through exchanges adds: $$ \frac{n-1}{k-1} $$

Simplified Geometric Series - Combining all, the total number of bottles you can drink simplifies to:

$$ \text{Total} = n + \frac{n-1}{k-1} $$

Code

1
2
3
4
5
6
7

class Solution {
public:
  int numWaterBottles(int numBottles, int numExchange) {
    if (numExchange <= 1) return numBottles;
    return numBottles + (numBottles - 1) / (numExchange - 1);
  }
};
1
2
3
4
5
6
7
8

package main

func numWaterBottles(numBottles int, numExchange int) int {
  if numExchange <= 1 {
    return numBottles
  }
  return numBottles + (numBottles-1)/(numExchange-1)
}
1
2
3
4
5

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
}
1
2
3
4
5
6

class Solution {
  fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
    if (numExchange <= 1) return numBottles
    return numBottles + (numBottles - 1) / (numExchange - 1)
  }
}
1
2
3
4
5

class Solution:
  def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
    if numExchange <= 1:
      return numBottles
    return numBottles + (numBottles - 1) // (numExchange - 1)
1
2
3
4
5
6

impl Solution {
  pub fn num_water_bottles(num_bottles: i32, num_exchange: i32) -> i32 {
    if num_exchange <= 1 { return num_bottles; }
    num_bottles + (num_bottles - 1) / (num_exchange - 1)
  }
}
1
2
3
4

function numWaterBottlesFormula(numBottles: number, numExchange: number): number {
  if (numExchange <= 1) return numBottles;
  return numBottles + Math.floor((numBottles - 1) / (numExchange - 1));
}

Complexity

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