Find Water In A Glass

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 2 4 
2 2 2
Sample Output 1 :
0.5
0.5
Explanation Of Sample Input 1 :
         1
      2     3
   4     5     6

3L of water will fill the first 3 glasses completely. When the fourth litre is poured, the water drops to glasses 2 and 3 from 1, and then to glasses 4, 5, and 6. 

Notice that glass 5 receives water from both glasses 2 and 3, whereas glasses 4 and 6 receive water only from one glass each. Hence the water in glass 5 is 0.5L and water in glasses 4 and 6 is 0.25L each.

Hence the water in glass 5 is 0.5L.
Sample Input 2 :
2
1 1 1
3 3 4
Sample Output 2 :
1
0.25
Hint

 Perform a DFS from top to bottom transporting water.

Approaches (2)
Brute Force - using DFS

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 : 

  1. Assign all water to the topmost glass.
  2. 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
  3. Return glass[n][m]
Time Complexity

O( 2^N ), Where ‘N’ number of rows in the matrix. 

 

As for every element, we recurse over 2 elements that are below it.  

Hence the time complexity is O( 2^N ). 

Space Complexity

O( N^2 ). Where ‘N’ number of rows in the matrix. 

 

As we are using a 2D array to keep track of water in each glass. 

Hence the space complexity is O( N^2 ).

Code Solution
(100% EXP penalty)
Find Water In A Glass
Full screen
Console