CareerCup

1) Sort the array
2) Scan array from 0 to n/2
3) for each element i in array:
a) find index of a number which is <= 2*a[i]. Take diff of array size - index of the number.  add this diff with index i (away from 0th index). make it min
b) repeat step 3.a and take min

Same qns was asked to me. I sorted the array then started from the end comparing with a[0]. If a[0]x2 >= a[end] then fine else keep on decrementing. Answer is the number of decrements made. It passed 3 out of 4 test cases.

int min_elems(int a[],int end,int start) //a is sorted array
{
	if(start >= end) return 999;
	if(a[end] <= 2*a[start]) return 0;
	return 1+min(min_elems(a,end,start+1) ,min_elems(a,end-1,start));
}

int find_min_no_of_elem(int *arr, int size)
{
int i,j, temp;
int index[size];
int count=0;
//Sort the array
for(i=0;i<size;i++)
{
for(j=0;j<size-i-1;j++)
if(*(arr+j) > *(arr+j+1))
{
temp = *(arr+j);
*(arr+j) = *(arr+j+1);
*(arr+j+1) = temp;
}
}

//find the distance
for(i=0;i<size;i++)
{
for(j=i;j<size;j++)
{
if(*(arr+i)*2 < *(arr+j))
{
index[i] = j;
break;
}
else
index[i]=0;
}
}


for(i=0;i<size;i++)
{
if(index[i]!=0)
count++;
}
return count;
}

import java.util.Arrays;
import java.util.Scanner;

public class test1 {

	public static void main(String[] args) {
	
		Scanner s = new Scanner(System.in);
		int len = s.nextInt();
		int a [] = new int[len],i=0,start=0,start1=0,end=len-1,end1=len-1,count=0,count1=0;
		boolean done=false,done1=false;
	
	while(s.hasNextInt())
	{
		
		a[i]= s.nextInt();
		i++;
		if (i==len)break;
	}
	Arrays.sort(a);
	
	
		for(i=0;i<len;i++)
		{
			if(a[end]<=2*a[start])
			{
				done=true;
			}
			else
			{
				count++;
				start++;
			}
			if(a[end1]<=2*a[start1])
			{
				done1=true;
			}
			else
			{
				count1++;
				end1--;
			}
						 
			if(done||done1)
			{
				if(count<=count1)
				System.out.println("Minimu elements to be removed " +count);
				else
				System.out.println("Minimu elements to be removed " +count1);
				break;
			}
			
		}
			
	}
}