# Algorithm for Glass of water

`There are some glasses with equal volume 1 liter. The glasses kept as follows`

1 2 3 4 5 6 7 8 9 10

You can put water to only top glass. If you put more than 1 liter water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..

If you have X liter of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.

Example. If you will put 2 litre on top.

1st â€“ 1 litre

2nd â€“ 1/2 litre

3rd - 1/2

Assume that every glass is full with water and we are adding 1 liter water from glass ONE, So see below how water is going to divided in all glasses.

Lets assume we have 7 level

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Water at each level : *[Assume that every glass is full with water and we are adding 1 liter water from glass ONE]*

Level 0 : 1

Level 1 : 1/2, 1/2

Level 2 : 1/4, 2/4, 1/4

Level 3 : 1/8, 3/8, 3/8, 1/8

Level 4 : 1/16, 4/16, 6/16, 4/16, 1/16

Level 5 : 1/32, 5/32, 10/32, 10/32, 5/32, 1/32

Level 6 : 1/64, 6/64, 15/64, 20/64, 15/64, 6/64, 1/64

As per above at ever level 1/2^Level_Number : For Level 0: 1/2^0 = 1

Here each glass has capacity of 1 liter.

So for X liter of water at each level

Level 1 : X-1

Level 2 : [X-1]-2

Level 3 : [X-1-2]-3

Level 4 : [X-1-2-3]-4

Level 5 : [X-1-2-3-4]-5

Level 6 : [X-1-2-3-4-5]-6

Level 7 : [X-1-2-3-4-5-6]-7

Here we are going to contract entire tree with use of matrix.

##### Algorithm

package com.omt.learn.algo; public class WaterGlass { static int CAPACITY_OF_GLASS = 1; public static void main(String[] args) { waterInGlass(11, 5, 2); } public static void waterInGlass(int x, int row, int glass) { int[][] matrix = new int[row][row]; for (int i = 0; i < row; i++) { matrix[i][0] = 1; matrix[0][i] = 1; } for (int i = 1; i < row; i++) { int k = i; for (int j = 1; j <= i; j++) { matrix[k][j] = matrix[k - 1][j] + matrix[k][j - 1]; k--; } } printMatrix(matrix); int r = row - 1; float usedWater = (r > 0 ? (float) ((r * (r + 1)) / 2) : 1.0f) * CAPACITY_OF_GLASS; float remainingWater = x - usedWater; float pow = (float) Math.pow(2, r); int g = glass - 1; float waterInGlass = remainingWater > 0 ? remainingWater * (matrix[r - g][g] / pow) : 0; System.out.println("Water In Glass :" + waterInGlass); } public static void printMatrix(int[][] i) { for (int[] p : i) { for (int px : p) { if (px > 9) { System.out.print(px + " "); } else { System.out.print(px + " "); } } System.out.println(); } } }