instagram

Algorithm for Glass of water

by omt

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

}
Share