CareerCup

1. Sort the array -- nlogn
2. take two index one at start and one at end.
3. let element1 and element2 are the two elements whose sum is closest to zero.
4. element1 = start
5. element2 = end

while(start<=end)
	{
	   if(abs(a[start] + element2) <= abs(element1 + element2))
	   {
		  element1 = a[start];
		  start++;
		  continue;
	   }
	   if(abs(a[end] + element1) <= abs(element2 + element1))
	   {
		  element2 = a[end];
		  end--;
		  continue;
	   }
	   
	   if(abs(a[start] + element2) > abs(element1 + element2) && abs(a[end] + element1) > abs(element2 + element1))
	   {
		   start++;
		   end--;
	   }
	}

Find 2 values closest to zero - O(n) - 2 passes

//dynamic programming. O(n^2)
void f(int[] s)
{
  if(s==null || s.len<2) return;

  int min=MAX;//min is the min distance to 0. which is non-negative.
  int minA, minB; // the indexes of elements in s whose sum is closest to 0.
  for(i=1;i<s.len;++i)
  {
    lmin=MAX;
    for(j=0;j<i;++j)
    {
      lmin=min(lmin,|s[i]+s[j]|);
      if(lmin==0)
      {
        print(lmin,i,j);
        return;
      }
    }  

    if(min>lmin)
    {
      min=lmin;
      minA=i;
      minB=j;
    }   
  }

  print(min, minA, minB);
}

I got on solution n(logn):
1. use 0 minus each element in the array, put result in a new array --- n
2. binary search each element in new array within old array, record distance. --- nlogn
3. pick the one with smallest distance --- n

The Simple Solution is ..,
1. Sort the array O(nlogn) .
2. Find the index of first positive and first negative number . O(n).
3. Start subtracting positive number from negative numbers until you find a value which is close to zero.

Hash all the values and then find if sum-number is available in the hash. Now if number = sum/2, you need to handle it separately.

O(n) Solution.

currentbestpair[2] = [a[0],a[1]];
currentbestpairval = abs((a[0]+a[1]-0)
for(i=2;i<n-1;i++) {
currentval = abs(currentbestpair[0]+a[i])-0);
if(currentval < currentbestval) {
currentbestpair[1] = a[i];
currentbestpairval = currentval;
}
currentval = abs(currentbestpair[1]+a[i])-0);
if(currentval < currentbestval) {
currentbestpair[0] = a[i];
currentbestpairval = currentval;
}
}

I got a solution in O(n). The logic is to find the max_negetive number and min_positive number. Please let me know if they are correct.

#include<stdio.h>
#include<stdlib.h>

int main()
{
  int a[6];
  int i;
  int zero_present = -1;

  int min_positive;
  int max_negetive;

  for(i=0;i<6;i++)
  {
   scanf("%d",&a[i]);
  }
  min_positive = -1;
  max_negetive = 0;

  for(i=0;i<6;i++)
  {
    if(a[i] > 0)
    {
     if(min_positive == -1)
         min_positive = a[i];
     else if(a[i] < min_positive)
        min_positive = a[i];
    }

    else if(a[i]==0)
      zero_present = i;
    else
    {
       if(max_negetive == 0)
          max_negetive = a[i];
       else if(a[i] > max_negetive)
          max_negetive = a[i];
    }
  }
 //Sum of min_positive and max_negetive will give the sum closest to zero
  if(min_positive == -1 || max_negetive == 0)
  {
      if(zero_present)
      {
         if(min_positive == -1)
            printf("%d\n",max_negetive); //closest sum to zero
         else
            printf("%d\n",min_positive);//closest sum
      }
      else
        printf("Such sum not possible\n");
  }
  else
     printf("%d\n",min_positive+max_negetive);


  return 0;
}

1.sort the array
2.find min element
3.compare the sun of min+left and min+right to find the ans

i mean find min element in term of distance from 0

Given an array A of n integers, give an ecient algorithm to check whether there are
two numbers in A whose sum is zero.