# 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] = 1;
matrix[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();
}
}

}
```