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 <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7double champagneTower(int poured, int query_row, int query_glass) {
8 vector<vector<double>> dp(101, vector<double>(101, 0.0));
9 dp[0][0] = poured;
10 for (int i = 0; i < 100; ++i) {
11 for (int j = 0; j <= i; ++j) {
12 if (dp[i][j] >= 1) {
13 double overflow = (dp[i][j] - 1) / 2.0;
14 dp[i + 1][j] += overflow;
15 dp[i + 1][j + 1] += overflow;
16 }
17 }
18 }
19 return min(1.0, dp[query_row][query_glass]);
20}
21
22int main() {
23 cout << fixed << setprecision(5) << champagneTower(2, 1, 1) << endl;
24 return 0;
25}We create a 2-D vector 'dp' to simulate the champagne distribution. For each glass, if it overflows, we distribute the overflow equally to the next row.
Instead of using a 2D array, we use a single array to minimize space usage. This array tracks only the current row and is updated row-by-row in place, calculating overflows accordingly.