Remove Minimum Elements

Remove Minimum Elements

  August 19, 2017    

---

Problem:

Given an unsorted array, trim the array such that twice of minimum is greater than maximum in the trimmed array. Elements should be removed either end of the array. Number of removals should be minimum

Explanation :

Here we will check with gap 0 to n so that we can check every element occurrence and find out min / max elements and check for the property if it violates then check for minimum(tb[i+1][j]+1,tb[i][j-1]+1).

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

class hackerranksolutionc

 {

     public static int max(int arr[],int start,int end)

     {

        int mx=arr[start];

        for(int i=start+1;i<=end;i++)

        {if(mx<arr[i])

        mx=arr[i];}

        return mx;

     }

     

     public static int min(int arr[],int start,int end)

     {

        int mx=arr[start];

        for(int i=start+1;i<=end;i++)

         {if(mx>arr[i])

        mx=arr[i];}

        return mx;

     }

public static void main (String[] args)

{

Scanner ab=new Scanner(System.in);

int t=ab.nextInt();

while(t-->0)

{

   int n=ab.nextInt();

   int i,j,max,min;

   int arr[]=new int[n];

   for( i=0;i<n;i++)

   arr[i]=ab.nextInt();

   int tb[][]=new int[n][n];

   for(int gap=0;gap<n;gap++)

   {

       for(i=0,j=gap;j<n;j++,i++)

       {

           max=max(arr,i,j);

           min=min(arr,i,j);

           tb[i][j]=(2*min>max)?0:Math.min(tb[i+1][j]+1,tb[i][j-1]+1);

       }

   }

   System.out.println(tb[0][n-1]);

}

}

}