## Similar Problems

Similar Problems not available

# Champagne Tower - Leetcode Solution

## Companies:

LeetCode: Champagne Tower Leetcode Solution

Difficulty: Medium

Topics: dynamic-programming

The Champagne Tower problem on Leetcode is a problem that requires finding the amount of champagne that will be poured at a specific glass in a champagne tower given the amount poured at the top glass.

Assuming that the liquid poured at the top glass evenly pours down to the glasses below, a formula can be derived that will help solve the problem. The basic formula is:

champagne(glass) = (champagne(glass_above) - 1)/2

where champagne(glass) is the amount of champagne at a specific glass and champagne(glass_above) is the amount of champagne in the glass immediately above.

The problem requires inputting the total poured champagne (poured), the number of rows (query_row), and the glass to be queried in the row (query_glass).

To solve the problem, the program must iterate through each row starting from the top and calculating the amount of champagne in each glass using the formula above.

Here's the detailed solution in Python:

```
def champagneTower(poured: int, query_row: int, query_glass: int) -> float:
#creating a two-dimensional array to represent the champagne tower
tower = [[0.0] * i for i in range(1, query_row + 2)]
tower[0][0] = poured #pouring champagne at the top glass
for i in range(query_row): #iterating through each row
for j in range(len(tower[i])): #iterating through each glass in the row
overflow = (tower[i][j] - 1) / 2 #calculating overflow champagne
if overflow > 0: #if there's overflow champagne, pour it down to the glasses below
tower[i+1][j] += overflow
tower[i+1][j+1] += overflow
return min(1, tower[query_row][query_glass]) #returning the amount of champagne at the queried glass
```

The program starts by creating a two-dimensional array to represent the champagne tower. The size of the array is based on the number of rows requested in the query. The program then pours champagne at the top glass (the first glass in the first row) and sets the remaining glasses to 0.

The program then iterates through each row starting from the first row. For each glass in the current row, the program calculates the overflow champagne that should be poured to the glasses below using the formula above. If there's overflow champagne, it is poured down to the glasses below by adding the amount to the next row's corresponding glass.

Finally, the program returns the amount of champagne at the queried glass. If the amount is greater than 1, it is limited to 1 as that is the maximum capacity of the glass.

## Champagne Tower Solution Code

`1`