Interview Question
//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);
}
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.
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;
}
I keep get the feeling that everybody here is mistakingly thinking that the answer must consist of one positive number and another negative number.
Look at {-100, -30, 1, 2, 7} for instance. The answer should be 1 and 2 since 3 is the closest sum the zero.
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
- Paras December 23, 2010