Sponsored
Sponsored
In this approach, we simulate the pouring process using a 2D array, where each element represents a glass and stores the amount of champagne in it. We iterate over each row, calculating the overflow and distributing it equally to the glasses directly below the current glass.
Time Complexity: O(n^2) where n is the number of rows traversed. Space Complexity: O(n^2) for the 2D array used to simulate the champagne distribution.
1#include <stdio.h>
2#include <string.h>
3
4#define MAX_ROWS 100
5
6double champagneTower(int poured, int query_row, int query_glass) {
7 double tower[MAX_ROWS][MAX_ROWS];
8 memset(tower, 0, sizeof(tower));
9 tower[0][0] = poured;
10
11 for (int i = 0; i <= query_row; ++i) {
12 for (int j = 0; j <= i; ++j) {
13 double overflow = (tower[i][j] - 1.0) / 2.0;
14 if (overflow > 0) {
15 tower[i+1][j] += overflow;
16 tower[i+1][j+1] += overflow;
17 }
18 }
19 }
20 return fmin(1.0, tower[query_row][query_glass]);
21}
22
23int main() {
24 printf("%.5f\n", champagneTower(2, 1, 1));
25 return 0;
26}In this implementation, we use a 2D array 'tower' to track champagne levels in glasses. We initially pour all champagne into the top glass and simulate champagne overflow row by row.
This approach optimizes the space complexity by using only a single array to store the champagne volumes, representing only two rows at a time.
Time Complexity: O(n^2). Space Complexity: O(n) due to the use of the single array.
1#include <iostream>
2#include <vector>
#include <algorithm>
using namespace std;
double champagneTower(int poured, int query_row, int query_glass) {
vector<double> dp(101, 0.0);
dp[0] = poured;
for (int i = 0; i < query_row; ++i) {
for (int j = i; j >= 0; --j) {
double overflow = (dp[j] - 1) / 2.0;
if (overflow > 0) {
dp[j + 1] += overflow;
dp[j] = 1.0;
}
}
}
return min(1.0, dp[query_glass]);
}
int main() {
cout << fixed << setprecision(5) << champagneTower(2, 1, 1) << endl;
return 0;
}We employ a single array 'dp' to store the champagne levels for the current active row. As we iterate over each row, we continuously update this array, simulating the overflow to the next row using inplace updates.