Tuesday, December 9, 2008

3 sum problem

The problem is defined as given a array find a set of elements such that c=a+b.

1. Sort the array
2. for each element c=arr[i] in the array
3. left=0; right=i;
4. while left<right
5. check if c==arr[left]+arr[right]
6. then add c to output
7. else if c<arr[left]+arr[right] right--
8. else left++
9. end

#include <iostream>

using namespace std;

int compare (const void * a, const void * b);
void sum3(int arr[], int n);
void main(){
int arr[]={2,3,5,1,4,9};



void sum3(int arr[], int n){
int l,r;
int count=0;
int index[6];
int curr=0;
for(int i=n-1;i>=0;i--)
l=0; r=i;
curr=arr[l] +arr[r];
if(arr[i] == curr){
cout<<arr[i]<<" ";
else if(arr[i] < curr)
else l++;
int compare (const void * a, const void * b)
return ( *(int*)a - *(int*)b );

Complexity of the above procedure is O(n^2). Apparently a better solution for the problem doesn't exist. Also, a number of problems can be reduced to the 3 sum problem and are called 3sum hard.

No comments:

Related Posts with Thumbnails