Last active
June 18, 2020 04:43
-
-
Save thmain/11301a3826f91cc35ee1f3a0092661d8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class EggDropRecursion { | |
public int getDrops(int eggs, int floors){ | |
//base case 1: | |
//if floors = 0 then no drops are required OR floors = 1 then 1 drop is required | |
if(floors==0 || floors==1) | |
return floors; | |
//base case 2: | |
//if only one egg is there then drops = floors | |
if(eggs==1) | |
return floors; | |
int minimumDrops=Integer.MAX_VALUE, tempResult; | |
//check dropping from all the floors 1 to floors and pick the minimum among those. | |
//for every drop there are 2 scenarios - a) either egg will break b) egg will not break | |
for (int i = 1; i <=floors ; i++) { | |
//for the worst case pick the maximum among a) and b) | |
tempResult = Math.max(getDrops(eggs-1,i-1), getDrops(eggs, floors-i)); | |
minimumDrops = Math.min(tempResult,minimumDrops); | |
} | |
return minimumDrops + 1; | |
} | |
public static void main(String[] args) { | |
EggDropRecursion eggDropRecursion = new EggDropRecursion(); | |
int eggs = 2; | |
int floors = 10; | |
System.out.printf("(Recursion) Minimum number of drops required in worst case with eggs: | |
" + eggs + " and floors:" + floors + " is: " + eggDropRecursion.getDrops(eggs,floors)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment