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(); } } }