Find the amount of water in ith cup in a pyramid structure?

The pascal triangle solution for calculating binomial coefficient can be used to solve this problem. We just need to tweak the algorithm a little bit and instead of calculating binomial coefficients, we calculate the water level. Given ith cup, we calculate level and index to find out where the cup sits in the triangle.

The cups are modelled as

    0         Level 1
  1   2       Level 2
3   4   5     Level 3

getIndex() and getLevel() returns the index and level. Index and Level starts at 1.

public static int getIndex(int i) {
    int totalNodes = i + 1;
    double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2;
    int level = (int)Math.floor(d);
    int total = ((level+1)*(level+2))/2;
    int index = 0;
    if(total==totalNodes) index = level;
    else{
        level++;
        index = totalNodes - total - 1;
    }

    return ++index;
}

public static int getLevel(int i) {
    int totalNodes = i + 1;
    double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2;
    int level = (int)Math.floor(d);
    int total = ((level+1)*(level+2))/2;
    int index = 0;
    if(total==totalNodes) index = level;
    else{
        level++;
        index = totalNodes - total - 1;
    }

    return ++level;
}

k is kth cup starting at 0. C is cup capacity, L is total water.

public static double getWaterLevel(double C, double L, int k) {
    int n = getLevel(k);
    int index = getIndex(k);
    double[] water = new double[index+1];

    water[1] = L;

    for(int i = 2; i <= n; i++)
    {
        boolean overflowed = false;

        for(int j = Math.min(i, index); j > 0; j--) {
            double over = 0;
            if(water[j]>C) over = (water[j]-C)/2;
            if(water[j-1]>C) over += (water[j-1]-C)/2;

            water[j] = over;

            if(!overflowed && over!=0) overflowed=true;
        }

        if(!overflowed) break; // no more overflow. stop 
    }

    return water[index] > C ? C : water[index];
}

Here is another easy solution that simply pours the water into the current glass and then checks if there is extra water then flows to the next level. Here I have used 2D Mat for pouring the water. Then I have converted the 2D mat to 1D having size equals to ith element/glass which we need to return and return that. Implementation wise this is a very easy solution.

private double fillWaterInGlasses(double capacity, double water , int glassToFind) {
    int maxLevel = (int)(water/capacity)/2 + 1;
    double[][] glasses = new double[maxLevel][maxLevel];
    // Pour total water in top glass initially.
    glasses[0][0] = water;
    int level=0;
    boolean waterInLevel = true;
    while(waterInLevel) {
        waterInLevel = false;
        // For each glass in the level.
        for(int j=0; j<=level; j++) {
            // If the glass has more liquid then it can store then pour it to glasses under it.
            if(glasses[level][j] > capacity) {
                double extraWater = glasses[level][j] - capacity;
                glasses[level][j] = capacity;
                glasses[level+1][j] += extraWater / 2;
                glasses[level+1][j+1] += extraWater / 2;
                waterInLevel = true;
            }
        }
        level++;
    }
    double res[] = new double[glassToFind];
    int k =0;
    for (int i = 0; i < glasses.length; i++) {
        for (int j = 0; j <= i; j++) {
            res[k] = glasses[i][j];
            if (k == glassToFind-1){
                return res[glassToFind-1];
            }
            k++;
        }
    }
    return res[glassToFind-1];
}