# Given an array of integers, find count of minimum number of elements to be removed from the array such that the maximum element of the new array is at most twice of the minimum.

Our aim is to remove extreme numbers which are not in our required range.

So first we need to sort the array.

(In my code I have assumed the array is sorted. You can use any sorting algorithm)

We create a pointer first(shown in fig. in red) and last(shown in fig. in purple)

Calculate the number of elements to remove if first needs to be kept.

In our case it’s 6.

Do the same for last.

Again here it’s 6.

If elementsToRemoveToKeepFirst >= elementsToRemoveToKeepLast

We increment first.

Else we decrement last.

1st Step :

Increment first.

Now we check for our required condition that max element i.e last is atmost twice the min i.e first and stop.

Maximum : 8

Minimum : 4

So the Maximum is atmost twice minimum in the array.

#include<stdio.h> int NumOfElementsToRemove(int first,int last,int flag,int* arr){ int i,count=0; if(flag==0){ for(i=last;i>first;i--){ if(arr[i]>arr[first]*2) count++; else return count; } }else{ for(i=first;i<last;i++){ if(arr[last]>arr[i]*2) count++; else return count; } } } int main() { int arr[] = {2,4,5,6,7,8,15,19}; int size = sizeof(arr)/sizeof(int),i,j; int numRemove[size]; int first = 0,last = size-1,count=0; int elementsToRemoveToKeepFirst,elementsToRemoveToKeepLast; while(first<last){ if(arr[first]*2 >= arr[last]) break; else{ elementsToRemoveToKeepFirst = NumOfElementsToRemove(first,last,0,arr); elementsToRemoveToKeepLast = NumOfElementsToRemove(first,last,1,arr); if(elementsToRemoveToKeepFirst>=elementsToRemoveToKeepLast){ first++; }else{ last--; } count++; } } printf("Minimum Number of Elements to remove: %d",count); return 0; }