Water Bottles - Leetcode 1518 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
3:45 - Time Complexity
6:44 - Coding Explanation

leetcode 1518

#neetcode #leetcode #python

[krityaan]

For anyone curious about the O(1)

result = numBottles + floor((numBottles -1) / (numExchange - 1))

[hamirmahal]

Thanks for the time complexity breakdown at 3:45. If you added a "sequel" video with a constant time solution and proof, I'd watch it.

[souviksarkark]

You always make it so clear. It will be great if we get problem 4 explanation of Leetcode weekly contests.

[CuriousAnonDev]

How about a live stream where you give leetcode weekly/biweekly live!

[dm]

I think for the time complexity the base of the log doesn't matter.

[abhinavchoukse]

@NeetCodeIO Could you please post the solutions of leetcode contest every week... or livestream after the contest ends...??

[valentinrafael]

Lol, I actually went back to this problem today and got to this same log solution ( while at work ). THese kind of solutions are cool to look at, *after* you actually find a solution that helps you learn

The initial solution I submited to this problem was

count = 0

if count < numBottles:
count += 1
if count % x == 0:
numBottles += 1

return numBottles

[woodylucas]

I struggled with this problem. I knew I had to do some modular arithmetic, but I never realized the answer was right in front of me if I had just studied the picture.

[anonanon]

You can do it in O(1), here is a hint:
Think of the process as going both ways: you can exchange empty bottles for full ones but you can also exchange just water for empty bottles.

Exchange all water for bottles and then all bottles directly for water(without bottles).

Edge case: remember that you have to be left with at least one empty bottle at the end

[anirbanhossen]

Split Array into Fibonacci Sequence. make a video on this

[Levy]

got this one:

def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
drunk = numBottles

while numBottles >= numExchange:
numBottles, emptyBottles = divmod(numBottles, numExchange)
drunk += numBottles
numBottles += emptyBottles

return drunk

[nikhil]

My favorite part is that it is easy 😂😢

[reggiehurley]

there's a constant time solution as well

[jegadheeswarank]

Hello @neetcodeio whats your future plan

[WhosShamouz]

My solution kinda stinks, but got the job done:

class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
emptyBottles = numBottles
maxDrinkableWaters = numBottles
exchange = 101

while exchange != 0:
exchange = emptyBottles // numExchange #3
maxDrinkableWaters += exchange #12
emptyBottles = emptyBottles % numExchange + exchange #3

return maxDrinkableWaters