Program to find amount of water in a given glass | GeeksforGeeks

Program to find amount of water in a given glass | GeeksforGeeks
There are some glasses with equal capacity as 1 litre. The glasses are 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 litre water to 1st glass, water overflows and fills equally in both 2nd and 3rd glasses. Glass 5 will get water from both 2nd glass and 3rd glass and so on.
If you have X litre of water and you put that water in top glass, how much water will be contained by jth glass in ith row?
Time Complexity: O(i*(i+1)/2) or O(i^2)
Auxiliary Space: O(i*(i+1)/2) or O(i^2)

// Returns the amount of water in jth glass of ith row

float findWater(int i, int j, float X)

{

    // A row number i has maximum i columns. So input column number must

    // be less than i

    if (j > i)

    {

        printf("Incorrect Input\n");

        exit(0);

    }

    // There will be i*(i+1)/2 glasses till ith row (including ith row)

    float glass[i * (i + 1) / 2];

    // Initialize all glasses as empty

    memset(glass, 0, sizeof(glass));

    // Put all water in first glass

    int index = 0;

    glass[index] = X;

    // Now let the water flow to the downward glassses till the

    // amount of water X is not 0 and row number is less than or

    // equal to i (given row)

    for (int row = 1; row <= i && X !=0.0; ++row)

    {

        // Fill glasses in a given row. Number of columns in a row

        // is equal to row number

        for (int col = 1; col <= row; ++col, ++index)

        {

            // Get the water from current glass

            X = glass[index];

            // Keep the amount less than or equal to

            // capacity in current glass

            glass[index] = (X >= 1.0f) ? 1.0f : X;

            // Get the remaining amount

            X = (X >= 1.0f) ? (X - 1) : 0.0f;

            // Distribute the remaining amount to the down two glasses

            glass[index + row] += X / 2;

            glass[index + row + 1] += X / 2;

        }

    }

    // The index of jth glass in ith row will be i*(i-1)/2 + j - 1

    return glass[i*(i-1)/2 + j - 1];

}

Read full article from Program to find amount of water in a given glass | GeeksforGeeks