Last Updated: 5 Jun, 2022
Find Water In A Glass
Moderate
Eric has an arrangement of infinite glasses, similar to a pascal’s triangle, as shown below.
1
2 3
4 5 6
7 8 9 10 … and so on
The glasses are all empty and can contain exactly 1 Litre of water each. You can pour water only on the topmost glass (glass with number 1).
When the topmost glass 1 is full, the remaining water will fall into glasses 2 and 3.
For example, if you pour 2 Litres of water,
Glass 1 will be completely full after 1 Litre is poured,
The second litre of water will then flow to glasses 2 and 3, filling 0.5 Litres in both of these glasses.
Eric wants you to find the amount of water in ‘M’th glass in the ‘N’th row, if you are allowed to pour exactly ‘W’ Litres of water.
Find the amount of water in Litres in the ‘M’ glass in the ‘N’th row.
Example:
Input: ‘N’ = ‘2’, 'M' = ‘2’, ‘W’ = ‘2’
Output: 0.5
1
2 3
In the above example, glass ‘1’ is completely filled after 1 litre of water is poured into it. Then the remaining water is dropped into glasses 2 and 3, filling half of each of them.
Hence, the 2nd glass in the 2nd row is Glass 3, which has 0.5L of water.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
For each test case, the first line contains three integers ‘N’ and ‘M’ denoting the row and column of the glass and ‘W’ denoting the number of litres of water poured.
Output format :
For each test case, print a single integer representing the amount of water in the ‘M’th column of the ‘N’th row.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= M <= N <= 100
1 <= W <= 10^6
Time Limit: 1 sec
Approaches
We will maintain a 2D array ‘glass’ where glass[i][j] represents the amount of water in the ‘j’th glass of the ‘i’th row. We start a DFS from the topmost glass, and from the topmost glass to the bottom-most glass.
At every step, we check if there is enough water for it to fill the current glass. If there is, we fill the current glass, and pass on the rest of the water to the below two glasses. This process is repeated in a recursive manner until the water is over or we reach the desired cell in the 2D array.
At any point of time, if for the ‘x’th glass, we have <1L of water, then we assign all the remaining water to the current glass and pass on no water to the below glasses.
The process of passing the water to below glasses is as follows:
Water in the glass, glass[i][j] will be passed on to glass[i+1][j] and glass[i+1][j-1].
The steps are as follows :
- Assign all water to the topmost glass.
- Transfer water to all below glasses using dfs as follows
- if water overflows,
- Transfer to left glass half of remaining water
- Transfer to right glass half of remaining water
- Else:
- Keep all water in the same glass, no overflow
- if water overflows,
- Return glass[n][m]
We can observe that the water completely goes from the topmost row to the bottom-most row. If we fill up the i’th row first, when all glasses are full, or they do not overflow anymore, we can move on to the next row.
At any point in time, if for the ‘x’th glass, we have <1L of water, then we assign all the remaining water to the current glass and pass on no water to the below glasses.
The process of passing the water to below glasses is as follows:
Water in the glass, glass[i][j] will be passed on to glass[i+1][j-1] and glass[i+1][j].
These steps remain the same as the Brute force approach, but we complete one row before moving on to the next, which makes the approach way more efficient.
The steps are as follows :
- Assign all water to topmost glass.
- Start iterating from the topmost row, left to right
- For each glass, transfer water to below glasses as follows
- if water overflows,
- Transfer to left glass half of remaining water
- Transfer to right glass half of remaining water
- Else:
- Keep all water in the same glass, no overflow.
- if water overflows,
- Return glass[n][m]