fork(4) download 
  1. class PyramidOfGlassAndWater {
  2.  
  3. 	/**
  4. There are some glasses with equal capacity as 1 litre. The glasses are kept as follows:
  5.  
  6.     			   1
  7. 		         2   3
  8. 		      4    5    6
  9. 		    7    8    9   10
  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.
  11. 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?
  12.  
  13. Example. If you will put 2 litre on top.
  14. 1st – 1 litre
  15. 2nd – 1/2 litre
  16. 3rd – 1/2 litre
  17.  
  18. I have thought of a recursive approach. This approach is easy to understand and memory efficient.
  19.  
  20. Consider that rows are numbered starting from 1 and columns are numbered from 1.
  21. So triangle will look like.
  22.  
  23. 			            1				-> Row 1
  24. 			        1		2			-> Row 2
  25. 			    1	    2	    3		-> Row 3
  26. 			1		2		3		4	-> Row 4
  27.  
  28. Input is amount poured at topmost glass and required rownumber and column number.
  29.  
  30. For a given glass if water is poured on it; then it can store only 1 unit; 
  31. and remaining water is divided into half and passed to right child and left child.
  32. So amount passed to each child  = (amount at this glass -1) /2
  33. Its children will have row number as (current row number +1)
  34. Its left child will have column number same as current cup
  35. Its right child will have column number as (current column number +1)
  36.  
  37. So start with topmost glass as current glass.
  38. If required row number matches 
  39.        then if required column matches amount is minimum(1,actual amonut)
  40.        otherwise it is other cup of same row. So no need to go further down
  41. else i.e. row does not match then 
  42.        call the same function to get the amount of water in required cup by pouring water in left child 
  43.        call the same function to get the amount of water in required cup by pouring water in right child 
  44.        sum two amounts to get total amount from both path.
  45.        value in the cup min(1, above sum) 
  46.        
  47.        SAMPLE OUTPUT 
  48.        
  49.        	    findWaterInGlass(10,1,1)=1.0
  50. 			findWaterInGlass(10,2,1)=1.0
  51. 			findWaterInGlass(10,2,2)=1.0
  52. 			findWaterInGlass(10,3,1)=1.0
  53. 			findWaterInGlass(10,3,2)=1.0
  54. 			findWaterInGlass(10,3,3)=1.0
  55. 			findWaterInGlass(10,4,1)=0.375
  56. 			findWaterInGlass(10,4,2)=1.0
  57. 			findWaterInGlass(10,4,3)=1.0
  58. 			findWaterInGlass(10,4,4)=0.375
  59. 			findWaterInGlass(10,5,1)=0.0
  60. 			findWaterInGlass(10,5,2)=0.0
  61. 			findWaterInGlass(10,5,3)=0.0
  62. 			findWaterInGlass(10,5,4)=0.0
  63. 			findWaterInGlass(10,5,5)=0.0
  64. 	 *    
  65. 	 */
  66.  
  67. 	public static float findWaterInGlass(float inputAtTop, int rownum,int colnum){
  68. 		return findWaterInGlassInternal(inputAtTop,1,1,rownum,colnum);
  69. 	}
  70.  
  71. 	public static float findWaterInGlassInternal(float input,int currentRow,int currentCol, int requiredRown,int requiredColnum){
  72. 		if(requiredColnum>requiredRown) throw new RuntimeException("requiredColnum>requiredRown");
  73. 		if(currentRow==requiredRown){
  74. 			if(currentCol==requiredColnum) 
  75. 				return min(input,1);
  76. 			else
  77. 				return 0;
  78. 		}else{
  79. 			// Pour water in right side and in left side equally
  80. 			float waterForNextLevel = (input-1)/2;
  81. 			if(waterForNextLevel>0){
  82. 				float waterFromLeftBranch= findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol,requiredRown,requiredColnum) ; 
  83. 				float waterFromRightBranch	= findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol+1,requiredRown,requiredColnum);
  84. 				return min(waterFromLeftBranch+waterFromRightBranch,1);
  85. 			}else{
  86. 				return 0;
  87. 			}
  88. 		}
  89. 	}
  90. 	public static void main(String[] args) {
  91. 		int totalRounum =5;
  92. 		int waterQuantity =10;
  93. 		for(int i=1;i<=totalRounum;i++){
  94. 			for(int j=1;j<=i;j++){
  95. 				System.out.println("findWaterInGlass("+waterQuantity+","+i+","+j+")="+ findWaterInGlass(waterQuantity,i,j));
  96. 			}
  97. 		}
  98.  
  99. 	}
  100. 	public static float  min(float a, float b){
  101. 		return a<b?a:b;
  102. 	}
  103. }
  104.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
findWaterInGlass(10,1,1)=1.0
findWaterInGlass(10,2,1)=1.0
findWaterInGlass(10,2,2)=1.0
findWaterInGlass(10,3,1)=1.0
findWaterInGlass(10,3,2)=1.0
findWaterInGlass(10,3,3)=1.0
findWaterInGlass(10,4,1)=0.375
findWaterInGlass(10,4,2)=1.0
findWaterInGlass(10,4,3)=1.0
findWaterInGlass(10,4,4)=0.375
findWaterInGlass(10,5,1)=0.0
findWaterInGlass(10,5,2)=0.0
findWaterInGlass(10,5,3)=0.0
findWaterInGlass(10,5,4)=0.0
findWaterInGlass(10,5,5)=0.0
https://ideone.com/2ecUuD
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!