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 the 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 a top glass, how much water will be contained by the jth glass in an ith row?
Example. If you will put 2 litres on top.
1st – 1 litre
2nd – 1/2 litre
3rd – 1/2 litre
For 2 Liters Water
The approach is similar to Method 2 of the Pascal’s Triangle. If we take a closer look at the problem, the problem boils down to Pascal’s Triangle.
1 ---------------- 1
2 3 ---------------- 2
4 5 6 ------------ 3
7 8 9 10 --------- 4
Each glass contributes to the two glasses down the glass. Initially, we put all water in the first glass. Then we keep 1 litre (or less than 1 litre) in it and move rest of the water to two glasses down to it. We follow the same process for the two glasses and all other glasses till the ith row. There will be i*(i+1)/2 glasses till ith row.
C++
// Program to find the amount of water in j-th glass// of i-th row#include <stdio.h>#include <stdlib.h>#include <string.h>// Returns the amount of water in jth glass of ith rowfloat 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 Inputn"); 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 glasses // till the row number is less than or/ equal to i (given row) // correction : X can be zero for side glasses as they have lower rate to fill for (int row = 1; row <= i ; ++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];}// Driver program to test above functionint main(){ int i = 2, j = 2; float X = 2.0; // Total amount of water printf("Amount of water in jth glass of ith row is: %f", findWater(i, j, X)); return 0;} |
Java
// Program to find the amount /// of water in j-th glass// of i-th rowimport java.lang.*;class GFG{// Returns the amount of water// in jth glass of ith rowstatic float findWater(int i, int j, float X){// A row number i has maximum i // columns. So input column // number must be less than iif (j > i){ System.out.println("Incorrect Input"); System.exit(0);}// There will be i*(i+1)/2 glasses // till ith row (including ith row)int ll = Math.round((i * (i + 1) ));float[] glass = new float[ll + 2];// Put all water in first glassint index = 0;glass[index] = X;// Now let the water flow to the // downward glasses till the row // number is less than or/ equal // to i (given row) // correction : X can be zero for side // glasses as they have lower rate to fillfor (int row = 1; row <= i ; ++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 - 1return glass[(int)(i * (i - 1) / 2 + j - 1)];}// Driver Codepublic static void main(String[] args){ int i = 2, j = 2; float X = 2.0f; // Total amount of water System.out.println("Amount of water in jth " + "glass of ith row is: " + findWater(i, j, X));}}// This code is contributed by mits |
Python3
# Program to find the amount # of water in j-th glass of# i-th row# Returns the amount of water # in jth glass of ith rowdef findWater(i, j, X): # A row number i has maximum # i columns. So input column # number must be less than i if (j > i): print("Incorrect Input"); return; # There will be i*(i+1)/2 # glasses till ith row # (including ith row) # and Initialize all glasses # as empty glass = [0]*int(i *(i + 1) / 2); # Put all water # in first glass index = 0; glass[index] = X; # Now let the water flow to # the downward glasses till # the row number is less # than or/ equal to i (given # row) correction : X can be # zero for side glasses as # they have lower rate to fill for row in range(1,i): # Fill glasses in a given # row. Number of columns # in a row is equal to row number for col in range(1,row+1): # Get the water # from current glass X = glass[index]; # Keep the amount less # than or equal to # capacity in current glass glass[index] = 1.0 if (X >= 1.0) else X; # Get the remaining amount X = (X - 1) if (X >= 1.0) else 0.0; # Distribute the remaining # amount to the down two glasses glass[index + row] += (X / 2); glass[index + row + 1] += (X / 2); index+=1; # The index of jth glass # in ith row will # be i*(i-1)/2 + j - 1 return glass[int(i * (i - 1) /2 + j - 1)];# Driver Codeif __name__ == "__main__": i = 2; j = 2; X = 2.0; # Total amount of water res=repr(findWater(i, j, X)); print("Amount of water in jth glass of ith row is:",res.ljust(8,'0'));# This Code is contributed by mits |
C#
// Program to find the amount // of water in j-th glass// of i-th rowusing System;class GFG{// Returns the amount of water// in jth glass of ith rowstatic float findWater(int i, int j, float X){// A row number i has maximum i // columns. So input column // number must be less than iif (j > i){ Console.WriteLine("Incorrect Input"); Environment.Exit(0);}// There will be i*(i+1)/2 glasses // till ith row (including ith row)int ll = (int)Math.Round((double)(i * (i + 1)));float[] glass = new float[ll + 2];// Put all water in first glassint index = 0;glass[index] = X;// Now let the water flow to the // downward glasses till the row // number is less than or/ equal // to i (given row) // correction : X can be zero // for side glasses as they have// lower rate to fillfor (int row = 1; row <= i ; ++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 - 1return glass[(int)(i * (i - 1) / 2 + j - 1)];}// Driver Codestatic void Main(){ int i = 2, j = 2; float X = 2.0f; // Total amount of water Console.WriteLine("Amount of water in jth " + "glass of ith row is: " + findWater(i, j, X));}}// This code is contributed by mits |
PHP
<?php// Program to find the amount // of water in j-th glass of// i-th row// Returns the amount of water // in jth glass of ith rowfunction findWater($i, $j, $X){ // A row number i has maximum // i columns. So input column // number must be less than i if ($j > $i) { echo "Incorrect Input\n"; return; } // There will be i*(i+1)/2 // glasses till ith row // (including ith row) // and Initialize all glasses // as empty $glass = array_fill(0, (int)($i * ($i + 1) / 2), 0); // Put all water // in first glass $index = 0; $glass[$index] = $X; // Now let the water flow to // the downward glasses till // the row number is less // than or/ equal to i (given // row) correction : X can be // zero for side glasses as // they have lower rate to fill for ($row = 1; $row < $i ; ++$row) { // Fill glasses in a given // row. Number of columns // in a row is equal to row number for ($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.0) ? 1.0 : $X; // Get the remaining amount $X = ($X >= 1.0) ? ($X - 1) : 0.0; // Distribute the remaining // amount to the down two glasses $glass[$index + $row] += (double)($X / 2); $glass[$index + $row + 1] += (double)($X / 2); } } // The index of jth glass // in ith row will // be i*(i-1)/2 + j - 1 return $glass[(int)($i * ($i - 1) / 2 + $j - 1)];}// Driver Code$i = 2;$j = 2;$X = 2.0; // Total amount of waterecho "Amount of water in jth " , "glass of ith row is: ". str_pad(findWater($i, $j, $X), 8, '0');// This Code is contributed by mits?> |
Javascript
<script>// Program to find the amount /// of water in j-th glass// of i-th row// Returns the amount of water// in jth glass of ith rowfunction findWater(i , j, X){// A row number i has maximum i // columns. So input column // number must be less than iif (j > i){ document.write("Incorrect Input");}// There will be i*(i+1)/2 glasses // till ith row (including ith row)var ll = Math.round((i * (i + 1) ));glass = Array.from({length: ll+2}, (_, i) => 0.0);// Put all water in first glassvar index = 0;glass[index] = X;// Now let the water flow to the // downward glasses till the row // number is less than or/ equal // to i (given row) // correction : X can be zero for side // glasses as they have lower rate to fillfor (row = 1; row <= i ; ++row){ // Fill glasses in a given row. Number of // columns in a row is equal to row number for (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.0) ? 1.0 : X; // Get the remaining amount X = (X >= 1.0) ? (X - 1) : 0.0; // 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 - 1return glass[parseInt((i * (i - 1) / 2 + j - 1))];}// Driver Codevar i = 2, j = 2;var X = 2.0; // Total amount of waterdocument.write("Amount of water in jth " + "glass of ith row is: " + findWater(i, j, X)); // This code is contributed by 29AjayKumar </script> |
Output:
Amount of water in jth glass of ith row is: 0.500000
Time Complexity: O(i*(i+1)/2) or O(i^2)
Auxiliary Space: O(i*(i+1)/2) or O(i^2)
This article is compiled by Rahul and reviewed by neveropen team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Method 2 (Using BFS Traversal)
we will discuss another approach to this problem. First, we add a Triplet(row, col,rem-water) in the queue which indicates the starting value of the first element and fills 1-litre water. Then we simply apply bfs i.e. and we add left(row+1, col-1,rem-water) Triplet and right(row+1, col+1,rem-water) Triplet into the queue with half of the remaining water in first Triplet and another half into the next Triplet.
Following is the implementation of this solution.
C++
// CPP program for above approach#include<bits/stdc++.h>using namespace std;// Program to find the amount // of water in j-th glass // of i-th rowvoid findWater(float k, int i, int j){ // stores how much amount of water // present in every glass float dp[i+1][2*i + 1]; bool vis[i+1][2*i + 1]; // initialize dp and visited arrays for(int n=0;n<i+1;n++) { for(int m=0;m<(2*i+1);m++) { dp[n][m] = 0; vis[n][m] = false; } } // store Triplet i.e curr-row , curr-col queue<pair<int,int>>q; dp[0][i] = k; // we take the center of the first row for // the location of the first glass q.push({0,i}); vis[0][i] = true; // this while loop runs unless the queue is not empty while(!q.empty()) { // First we remove the pair from the queue pair<int,int>temp = q.front(); q.pop(); int n = temp.first; int m = temp.second; // as we know we have to calculate the // amount of water in jth glass // of ith row . so first we check if we find solutions // for the every glass of i'th row. // so, if we have calculated the result // then we break the loop // and return our answer if(i == n) break; float x = dp[n][m]; if(float((x-1.0)/2.0) < 0) { dp[n+1][m-1] += 0; dp[n+1][m+1] += 0; } else { dp[n+1][m-1] += float((x-1.0)/2.0); dp[n+1][m+1] += float((x-1.0)/2.0); } if(vis[n+1][m-1]==false) { q.push({n+1,m-1}); vis[n+1][m-1] = true; } if(vis[n+1][m+1]==false) { q.push({n+1,m+1}); vis[n+1][m+1] = true; } } if(dp[i-1][2*j-1]>1) dp[i-1][2*j-1] = 1.0; cout<<"Amount of water in jth glass of ith row is: "; // print the result for jth glass of ith row cout<<fixed<<setprecision(6)<<dp[i-1][2*j-1]<<endl;}// Driver Codeint main(){ //k->water in litres float k; cin>>k; //i->rows j->cols int i,j; cin>>i>>j; // Function Call findWater(k,i,j); return 0;} // This code is contributed by Sagar Jangra and Naresh Saharan |
Java
// Program to find the amount /// of water in j-th glass // of i-th row import java.io.*;import java.util.*;// class Triplet which stores curr row// curr col and curr rem-water // of every glass class Triplet{ int row; int col; double rem_water; Triplet(int row,int col,double rem_water) { this.row=row;this.col=col;this.rem_water=rem_water; }}class GFG{ // Returns the amount of water // in jth glass of ith row public static double findWater(int i,int j,int totalWater) { // stores how much amount of water present in every glass double dp[][] = new double[i+1][2*i+1]; // store Triplet i.e curr-row , curr-col, rem-water Queue<Triplet> queue = new LinkedList<>(); // we take the center of the first row for // the location of the first glass queue.add(new Triplet(0,i,totalWater)); // this while loop runs unless the queue is not empty while(!queue.isEmpty()) { // First we remove the Triplet from the queue Triplet curr = queue.remove(); // as we know we have to calculate the // amount of water in jth glass // of ith row . so first we check if we find solutions // for the every glass of i'th row. // so, if we have calculated the result // then we break the loop // and return our answer if(curr.row == i) break; // As we know maximum capacity of every glass // is 1 unit. so first we check the capacity // of curr glass is full or not. if(dp[curr.row][curr.col] != 1.0) { // calculate the remaining capacity of water for curr glass double rem_water = 1-dp[curr.row][curr.col]; // if the remaining capacity of water for curr glass // is greater than then the remaining capacity of total // water then we put all remaining water into curr glass if(rem_water > curr.rem_water) { dp[curr.row][curr.col] += curr.rem_water; curr.rem_water = 0; } else { dp[curr.row][curr.col] += rem_water; curr.rem_water -= rem_water; } } // if remaining capacity of total water is not equal to // zero then we add left and right glass of the next row // and gives half capacity of total water to both the // glass if(curr.rem_water != 0) { queue.add(new Triplet(curr.row + 1,curr.col - 1,curr.rem_water/2.0)); queue.add(new Triplet(curr.row + 1,curr.col + 1,curr.rem_water/2.0)); } } // return the result for jth glass of ith row return dp[i-1][2*j-1]; } // Driver Code public static void main (String[] args) { int i = 2, j = 2; int totalWater = 2; // Total amount of water System.out.print("Amount of water in jth glass of ith row is:"); System.out.format("%.6f", findWater(i, j, totalWater)); }} // this code is contributed by Naresh Saharan and Sagar Jangra |
Python3
# Program to find the amount # of water in j-th glass of i-th row# class Triplet which stores curr row# curr col and curr rem-water# of every glassclass Triplet: def __init__(self, row, col, rem_water): self.row = row self.col = col self.rem_water = rem_water# Returns the amount of water# in jth glass of ith rowdef findWater(i, j, totalWater): # stores how much amount of water present in every glass dp = [[0.0 for i in range(2*i+1)] for j in range(i+1)] # store Triplet i.e curr-row , curr-col, rem-water queue = [] # we take the center of the first row for # the location of the first glass queue.append(Triplet(0,i,totalWater)) # this while loop runs unless the queue is not empty while len(queue) != 0: # First we remove the Triplet from the queue curr = queue.pop(0) # as we know we have to calculate the # amount of water in jth glass # of ith row . so first we check if we find solutions # for the every glass of i'th row. # so, if we have calculated the result # then we break the loop # and return our answer if curr.row == i: break # As we know maximum capacity of every glass # is 1 unit. so first we check the capacity # of curr glass is full or not. if dp[curr.row][curr.col] != 1.0: # calculate the remaining capacity of water for curr glass rem_water = 1-dp[curr.row][curr.col] # if the remaining capacity of water for curr glass # is greater than then the remaining capacity of total # water then we put all remaining water into curr glass if rem_water > curr.rem_water: dp[curr.row][curr.col] += curr.rem_water curr.rem_water = 0 else: dp[curr.row][curr.col] += rem_water curr.rem_water -= rem_water # if remaining capacity of total water is not equal to # zero then we add left and right glass of the next row # and gives half capacity of total water to both the # glass if curr.rem_water != 0: queue.append(Triplet(curr.row + 1,curr.col - 1,(curr.rem_water/2))) queue.append(Triplet(curr.row + 1,curr.col + 1,(curr.rem_water/2))) # return the result for jth glass of ith row return dp[i - 1][2 * j - 1]i, j = 2, 2totalWater = 2 # Total amount of waterprint("Amount of water in jth glass of ith row is:", end = "")print("{0:.6f}".format(findWater(i, j, totalWater)))# This code is contributed by decode2207. |
C#
// Program to find the amount /// of water in j-th glassusing System;using System.Collections.Generic;class GFG { // class Triplet which stores curr row // curr col and curr rem-water // of every glass class Triplet { public int row, col; public double rem_water; public Triplet(int row, int col, double rem_water) { this.row = row; this.col = col; this.rem_water = rem_water; } } // Returns the amount of water // in jth glass of ith row public static double findWater(int i, int j, int totalWater) { // stores how much amount of water present in every glass double[,] dp = new double[i+1,2*i+1]; // store Triplet i.e curr-row , curr-col, rem-water List<Triplet> queue = new List<Triplet>(); // we take the center of the first row for // the location of the first glass queue.Add(new Triplet(0,i,totalWater)); // this while loop runs unless the queue is not empty while(queue.Count > 0) { // First we remove the Triplet from the queue Triplet curr = queue[0]; queue.RemoveAt(0); // as we know we have to calculate the // amount of water in jth glass // of ith row . so first we check if we find solutions // for the every glass of i'th row. // so, if we have calculated the result // then we break the loop // and return our answer if(curr.row == i) break; // As we know maximum capacity of every glass // is 1 unit. so first we check the capacity // of curr glass is full or not. if(dp[curr.row,curr.col] != 1.0) { // calculate the remaining capacity of water for curr glass double rem_water = 1-dp[curr.row,curr.col]; // if the remaining capacity of water for curr glass // is greater than then the remaining capacity of total // water then we put all remaining water into curr glass if(rem_water > curr.rem_water) { dp[curr.row,curr.col] += curr.rem_water; curr.rem_water = 0; } else { dp[curr.row,curr.col] += rem_water; curr.rem_water -= rem_water; } } // if remaining capacity of total water is not equal to // zero then we add left and right glass of the next row // and gives half capacity of total water to both the // glass if(curr.rem_water != 0) { queue.Add(new Triplet(curr.row + 1,curr.col - 1,curr.rem_water/2.0)); queue.Add(new Triplet(curr.row + 1,curr.col + 1,curr.rem_water/2.0)); } } // return the result for jth glass of ith row return dp[i - 1, 2 * j - 1]; } static void Main() { int i = 2, j = 2; int totalWater = 2; // Total amount of water Console.Write("Amount of water in jth glass of ith row is:"); Console.Write(findWater(i, j, totalWater).ToString("0.000000")); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Program to find the amount /// of water in j-th glass// of i-th row// class Triplet which stores curr row// curr col and curr rem-water// of every glassclass Triplet{ constructor(row,col,rem_water) { this.row=row; this.col=col; this.rem_water=rem_water; }}// Returns the amount of water // in jth glass of ith rowfunction findWater(i,j,totalWater){ // stores how much amount of water present in every glass let dp = new Array(i+1); for(let k=0;k<dp.length;k++) { dp[k]=new Array((2*i)+1); for(let l=0;l<dp[k].length;l++) { dp[k][l]=0; } } // store Triplet i.e curr-row , curr-col, rem-water let queue = []; // we take the center of the first row for // the location of the first glass queue.push(new Triplet(0,i,totalWater)); // this while loop runs unless the queue is not empty while(queue.length!=0) { // First we remove the Triplet from the queue let curr = queue.shift(); // as we know we have to calculate the // amount of water in jth glass // of ith row . so first we check if we find solutions // for the every glass of i'th row. // so, if we have calculated the result // then we break the loop // and return our answer if(curr.row == i) break; // As we know maximum capacity of every glass // is 1 unit. so first we check the capacity // of curr glass is full or not. if(dp[curr.row][curr.col] != 1.0) { // calculate the remaining capacity of water for curr glass let rem_water = 1-dp[curr.row][curr.col]; // if the remaining capacity of water for curr glass // is greater than then the remaining capacity of total // water then we put all remaining water into curr glass if(rem_water > curr.rem_water) { dp[curr.row][curr.col] += curr.rem_water; curr.rem_water = 0; } else { dp[curr.row][curr.col] += rem_water; curr.rem_water -= rem_water; } } // if remaining capacity of total water is not equal to // zero then we add left and right glass of the next row // and gives half capacity of total water to both the // glass if(curr.rem_water != 0) { queue.push(new Triplet(curr.row + 1,curr.col - 1,(curr.rem_water/2))); queue.push(new Triplet(curr.row + 1,curr.col + 1,(curr.rem_water/2))); } } // return the result for jth glass of ith row return dp[i-1][2*j-1];}// Driver Codelet i = 2, j = 2;let totalWater = 2; // Total amount of waterdocument.write("Amount of water in jth glass of ith row is:");document.write(findWater(i, j, totalWater).toFixed(6)); // This code is contributed by rag2127</script> |
Output
Amount of water in jth glass of ith row is:0.500000
Time Complexity: O(i^2)
Auxiliary Space: O(i^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
