Egg Droping Puzzle

Egg Droping Puzzle

  August 08, 2017    

---

Explanation:

First of all set all the column of row 0 with column value,
Set k for n=1 as for 1 egg we need n trails.

There is 2 condition that if a egg broke then n-1 trails needed and if not broken then maximum of floor-current floor trails needed.


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerrnaksolutionc
 {
     public static int show(int n,int k)
     {
         int arr[][]=new int[n+1][k+1];
         int res;
         for(int i=0;i<=n;i++)
         {
             arr[i][0]=0;
             arr[i][1]=1;
         }
         for(int i=1;i<=k;i++)
         arr[1][i]=i;
         for(int i=2;i<=n;i++)
         {
             for(int j=2;j<=k;j++)
             {
                 arr[i][j]=Integer.MAX_VALUE;
                 for(int x=1;x<=j;x++)
                 {
                     res=1+Math.max(arr[i-1][x-1],arr[i][j-x]);
                    if(res<arr[i][j])
                    arr[i][j]=res;      
                 }
             }
         }
         return arr[n][k];
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   System.out.println(show(ab.nextInt(),ab.nextInt()));
}
}
}