Pyramid Glass Drop

Pyramid Glass Drop

  October 13, 2018    

---

Problem:
We are given a pyramid of glasses , we need to find out how many glasses will fall down if one glass is removed.

Example if we remove 8 then 5 (4,5,2,3,1)glassed will fall down.


Intuition:

If we got to know the row number (in which row we are) then above two connected glasses will fall down
Hence recur for above glasses (but only once ,take 5 as example -> 2,3 ->1).

Idea is to use BFS/DFS.

DFS based solution:

import java.util.*;
import java.lang.*;
import java.io.*;
class solution
 {
   //can be optimized using bSearch
   public static int getRow(int n)
   {
     int row=1;
     while(row*(row+1)/2<n)
     ++row;
     return row;
   }
   public static int deleteBox(int cur,int row,boolean visited[])
   {
     if(cur<=0)
     return 0;
     if(cur==1 || row==1)
     {
       if(!visited[cur])
       {visited[cur]=true;
       return 1;}
     return 0;}
     if(row==0)
     return 1;
     visited[cur]=true;
     if(startOfRow(row,cur))
     {
       int r=getRight(cur,row);
       if(!visited[r])
       return 1+deleteBox(r,row-1,visited);
     }
     else if(endOfRow(row,cur))
     {
       int r=getLeft(cur,row);
       if(!visited[r])
       return 1+deleteBox(r,row-1,visited);
     }
     else
        {  int l=getLeft(cur,row);
          int r=getRight(cur,row);
          int res=0;
          if(!visited[l])
          res= 1+deleteBox(l,row-1,visited);
          if(!visited[r])
          res+= 1+deleteBox(r,row-1,visited);
          return res;}
          return 0;
   }
   public static boolean endOfRow(int n,int cur)
   {
     return n*(n+1)/2==cur;
   }
   public static boolean startOfRow(int n,int cur)
   {
     --n;
     return n*(n+1)/2==cur-1;
   }
   public static int fn(int n,boolean visited[])
   {
     int row=getRow(n);
     return deleteBox(n,row,visited)-1;
   }
   public static int getLeft(int n,int row)
   {
     return n-row;
   }

   public static int getRight(int n,int row)
   {
     return n-row+1;
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();;
      boolean visited[]=new boolean[n+1];
    System.out.println(fn(n,visited));
}
}
}