{"id":3520,"date":"2021-11-11T18:28:06","date_gmt":"2021-11-11T12:58:06","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3520"},"modified":"2021-11-11T18:28:07","modified_gmt":"2021-11-11T12:58:07","slug":"egg-dropping-puzzle","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/egg-dropping-puzzle\/","title":{"rendered":"Egg Dropping Puzzle"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-1-brute-forcerecursion\">Approach 1: Brute Force(Recursion)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-dynamic-programmingbottom-up\">Approach 2: Dynamic Programming(Bottom up)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>You are given <strong>A<\/strong> eggs, and you have access to a building with <strong>B<\/strong> floors from <strong>1<\/strong> to <strong>B<\/strong>.<\/p>\n\n\n\n<p>Each egg is identical in function, and if an egg breaks, you cannot drop it again.<\/p>\n\n\n\n<p>You know that there exists a floor <strong>C<\/strong> with <strong>0 &lt;= C &lt;= B<\/strong>&nbsp; such that any egg dropped at a floor higher than <strong>C<\/strong> will break, and any egg dropped at or below floor <strong>C<\/strong> will not break.<\/p>\n\n\n\n<p>Each move, you may take an egg (if you have an unbroken one) and drop it from any floor <strong>X<\/strong> (with <strong>1 &lt;= X &lt;= B<\/strong>).&nbsp;<\/p>\n\n\n\n<p>Your goal is to know with certainty what the value of <strong>C <\/strong>is.<\/p>\n\n\n\n<p>What is the minimum number of moves that you need to know with certainty what <strong>C<\/strong> is, regardless of the initial value of <strong>C<\/strong>?<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>A = 1, B = 2<strong><br><\/strong><strong>Output:<\/strong> 2<br><strong>Explanation:<\/strong><br><\/p>\n\n\n\n<ul><li>Drop the egg from floor 1.&nbsp; If it breaks, we know with certainty that F = 0.<\/li><li>Otherwise, drop the egg from floor 2.&nbsp; If it breaks, we know with certainty that F = 1.<\/li><\/ul>\n\n\n\n<p>&nbsp;If it didn&#8217;t break, then we know with certainty F = 2.<\/p>\n\n\n\n<ul><li>&nbsp;Hence, we needed 2 moves in the worst case to know what F is with certainty.<\/li><\/ul>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;A = 2, B = 10<\/p>\n\n\n\n<p><strong>Output:<\/strong> 4<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"949\"  height=\"670\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"critical floor\"  class=\"wp-image-3630 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 949px) 100vw, 949px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical-.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical-.png 949w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical--300x212.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical--768x542.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical--380x268.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical--550x388.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/critical--800x565.png 800w\" ><\/figure>\n\n\n\n<h2 id=\"approach-1-brute-forcerecursion\">Approach 1: Brute Force(Recursion)<\/h2>\n\n\n\n<p>The basic idea is, we have to find the minimum number of attempts to find the floor i.e. above that floor the egg will break and below that&nbsp; floor the egg will not break<\/p>\n\n\n\n<p>So, there are two choices<\/p>\n\n\n\n<ul><li>Egg will break<\/li><li>Egg will not break<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"771\"  height=\"820\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Brute Force\"  class=\"wp-image-3633 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 771px) 100vw, 771px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force.png 771w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-282x300.png 282w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-768x817.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-380x404.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Brute-Force-550x585.png 550w\" ><\/figure>\n\n\n\n<p>&nbsp;For <strong>Case 1:<\/strong><\/p>\n\n\n\n<ul><li>If the egg will break from a particular floor, go further below that floor.<\/li><\/ul>\n\n\n\n<p>For <strong>Case 2:<\/strong><\/p>\n\n\n\n<ul><li>&nbsp;For the second case if the egg will not break from a particular floor then we have to go<\/li><\/ul>\n\n\n\n<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;above to find the threshold floor.<\/p>\n\n\n\n<p><strong>Base Conditions:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"547\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Base Conditions\"  class=\"wp-image-3634 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions-300x160.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions-768x410.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions-380x203.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions-550x294.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Base-Conditions-800x427.png 800w\" ><\/figure>\n\n\n\n<p><strong>Algorithm :<\/strong><strong><br><\/strong><strong>&nbsp;<\/strong><\/p>\n\n\n\n<ul><li>Handle the base cases, when <strong>floors<\/strong> = 0 or 1<strong> <\/strong>and <strong>eggs = 1<\/strong>.<\/li><li>Run a loop from <strong>1<\/strong> to <strong>K<\/strong> and for each iteration, recurse for the case, if the <strong>egg<\/strong> breaks on the <strong>Xth floor <\/strong>or not and maximize it.<\/li><li>Also, minimize the minimum floor found so far.<\/li><li>Return the minimum floor.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int max(int a, int b) {\n  return (a > b) ? a : b;\n}\nint eggDrop(int n, int k) {\n  if (k == 1 || k == 0)\n    return k;\n \n  if (n == 1)\n    return k;\n \n  int min = INT_MAX, x, res;\n  for (x = 1; x &lt;= k; x++) {\n    res = max(\n      eggDrop(n - 1, x - 1),\n      eggDrop(n, k - x));\n    if (res &lt; min)\n      min = res;\n  }\n \n  return min + 1;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int eggDrop(int n, int k) {\n  if (k == 1 || k == 0)\n    return k;\n \n  if (n == 1)\n    return k;\n \n  int min = Integer.MAX_VALUE;\n  int x, res;\n  for (x = 1; x &lt;= k; x++) {\n    res = Math.max(eggDrop(n - 1, x - 1),\n      eggDrop(n, k - x));\n    if (res &lt; min)\n      min = res;\n  }\n \n  return min + 1;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import sys\n \n \ndef eggDrop(n, k):\n    if k == 1 or k == 0:\n        return k\n \n    if n == 1:\n        return k\n \n    min = sys.maxsize\n    for x in range(1, k + 1):\n \n        res = max(eggDrop(n - 1, x - 1), eggDrop(n, k - x))\n        if res &lt; min:\n            min = res\n \n    return min + 1<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(2^K), where K is total floors.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used<\/p>\n\n\n\n<h2 id=\"approach-2-dynamic-programmingbottom-up\">Approach 2: Dynamic Programming(Bottom up)<\/h2>\n\n\n\n<p>If you observe clearly, in the above recursive approach, there are overlapping sub-problems.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"584\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Bottom up\"  class=\"wp-image-3639 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-1024x584.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-1024x584.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-300x171.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-768x438.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-380x217.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-550x314.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up-800x456.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Bottom-up.png 1071w\" ><\/figure>\n\n\n\n<p>In the above image, <strong>E(2, 2)<\/strong> is being calculated twice, which can be stored in some table and can be retrieved in <strong>O(1)<\/strong>.<\/p>\n\n\n\n<p>Let us understand the <strong>dynamic programming <\/strong>approach with an example.<br><br><br>Let N = 3 and K = 6, i.e. there are <strong>3<\/strong> eggs and <strong>6 floors<\/strong>.<\/p>\n\n\n\n<p>Considering the base cases first as described above:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"316\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"dynamic programming approach\"  class=\"wp-image-3635 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1024x316.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1024x316.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-300x93.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-768x237.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-380x117.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-550x170.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-800x247.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1160x358.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach.png 1269w\" ><\/figure>\n\n\n\n<p>The recursive equation can be defined as :<\/p>\n\n\n\n<p><strong><em>F(N,K) = <\/em><\/strong>&nbsp;<strong><em>1+min{max( F(N-1,K &#8211; 1) , F(N, f &#8211; K) ) , k in 1:f}<\/em><\/strong><strong><em><br><\/em><\/strong><\/p>\n\n\n\n<p><strong>&nbsp;<\/strong>Using the above equation, the following table has been filled:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"316\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"dynamic programming approach 1\"  class=\"wp-image-3637 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-1024x316.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-1024x316.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-300x93.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-768x237.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-380x117.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-550x170.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-800x247.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1-1160x358.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/dynamic-programming-approach-1.png 1269w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"949\"  height=\"670\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3638 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 949px) 100vw, 949px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree.png 949w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree-300x212.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree-768x542.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree-380x268.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree-550x388.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/decision-tree-800x565.png 800w\" ><\/figure>\n\n\n\n<p><strong>Algorithm :<\/strong><strong><br><\/strong><strong>&nbsp;<\/strong><\/p>\n\n\n\n<ul><li>Initialise an 2D array <strong>eggfloor <\/strong>with size <strong>(N + 1) X (K + 1)<\/strong>.<\/li><li>Fill the first two columns of the table using the base cases as described.<\/li><li>Run a loop from <strong>i = 2 to N<\/strong> and a nested loop from <strong>j = 2 to K<\/strong>. For each <strong>jth<\/strong> iteration, run a loop from <strong>x<\/strong> from <strong>1 <\/strong>till <strong>j<\/strong>:<ul><li>Find the max of <strong>eggfloor[i &#8211; 1][x &#8211; 1] <\/strong>and <strong>eggfloor[i][j &#8211; x]<\/strong>.<\/li><li>Minimise the value of <strong>eggfloor[i][j]<\/strong>.<\/li><\/ul><\/li><li>Return the value of <strong>eggfloor[n][k]<\/strong>.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int eggDrop(int n, int k) {\n  int eggFloor[n + 1][k + 1];\n  int res;\n  int i, j, x;\n  for (i = 1; i &lt;= n; i++) {\n    eggFloor[i][1] = 1;\n    eggFloor[i][0] = 0;\n  }\n  for (j = 1; j &lt;= k; j++)\n    eggFloor[1][j] = j;\n \n  for (i = 2; i &lt;= n; i++) {\n    for (j = 2; j &lt;= k; j++) {\n      eggFloor[i][j] = INT_MAX;\n      for (x = 1; x &lt;= j; x++) {\n        res = 1 + max(\n          eggFloor[i - 1][x - 1],\n          eggFloor[i][j - x]);\n        if (res &lt; eggFloor[i][j])\n          eggFloor[i][j] = res;\n      }\n    }\n  }\n  return eggFloor[n][k];\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int eggDrop(int n, int k) {\n  int eggFloor[][] = new int[n + 1][k + 1];\n  int res;\n  int i, j, x;\n \n  for (i = 1; i &lt;= n; i++) {\n    eggFloor[i][1] = 1;\n    eggFloor[i][0] = 0;\n  }\n \n  for (j = 1; j &lt;= k; j++)\n    eggFloor[1][j] = j;\n \n  for (i = 2; i &lt;= n; i++) {\n    for (j = 2; j &lt;= k; j++) {\n      eggFloor[i][j] = Integer.MAX_VALUE;\n      for (x = 1; x &lt;= j; x++) {\n        res = 1 + max(\n          eggFloor[i - 1][x - 1],\n          eggFloor[i][j - x]);\n        if (res &lt; eggFloor[i][j])\n          eggFloor[i][j] = res;\n      }\n    }\n  }\n  return eggFloor[n][k];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">INT_MAX = 32767\n \n \ndef eggDrop(n, k):\n    eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]\n \n    for i in range(1, n + 1):\n        eggFloor[i][1] = 1\n        eggFloor[i][0] = 0\n \n    for j in range(1, k + 1):\n        eggFloor[1][j] = j\n \n    for i in range(2, n + 1):\n        for j in range(2, k + 1):\n            eggFloor[i][j] = INT_MAX\n            for x in range(1, j + 1):\n                res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x])\n                if res &lt; eggFloor[i][j]:\n                    eggFloor[i][j] = res\n \n    return eggFloor[n][k]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * K^2), where N is total eggs and K is the number of floors.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N*K), as dp array is used.<\/p>\n\n\n\n<p><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/egg-drop-problem\/\" target=\"_blank\" rel=\"noreferrer noopener\">Egg Drop Problem<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What are the special cases for the egg dropping puzzle?<\/strong><strong><br><\/strong>There are mainly two special cases for the egg dropping puzzle-<ol><li>If <strong>K = 0 or K = 1<\/strong>, the answer is <strong>K.<\/strong><\/li><li>If <strong>N = 1, <\/strong>the answer is<strong> K.<\/strong><\/li><\/ol><\/li><\/ul>\n\n\n\n<ul><li><strong>What is the efficient approach to solve the egg dropping puzzle?<\/strong><strong><br><\/strong>The dynamic programming approach is the most efficient approach to solve the problem. The time complexity is O(N*K^2) and space complexity is O(N*K).<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"You are given A eggs, and you have access to a building with B floors from 1 to&hellip;\n","protected":false},"author":5,"featured_media":3642,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[548],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3520"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3520"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3520\/revisions"}],"predecessor-version":[{"id":3690,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3520\/revisions\/3690"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3642"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}