how can i remove an array from an array?

What is the algorithmic approach, given an array of integers, to remove a minimum number of elements from the array such that the largest and the smallest number does not differ by more than two times?

• In other words if x is the minimum of the remaining elements in the array and y is the maximum than y<=2x Sample Test Case: Input: {4,5,3,8,3,7} Output: 2 Note: In the above sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.

• Answer:

  Sort the list.O(n*log(n)) The elements removed will either be smallest or the largest(prefixes or suffixes). If we remove i elements from beginning than the number of element that we need to remove(=j) from end can be found by searching(binary search) for 2*a[i]. Total elements removed = j+i. Find this number for all i and take minimum of this list. This will give the answer.O(n*log(n)) The second step can be reduced to O(n) but overall complexity will remain O(n*log(n)).