Thread: A faster algorithm

Hi,
I was told to write an algorithm as following
There are three arrays A[],B[],C[] of same size N.Find out all possible (i,j,k) such that A[i]+B[j]=C[k].The maximum allowed time complexity is O(N²).Following is the algorithm I wrtten for O(N²)

Code:

#include<stdio.h>

#define MAX 1000

struct sum
{
        int result;
        int i;
        int j;
};

int main()
{
        struct sum sum_array[MAX];
        int n=4;
        int a[] = {4,1,2,5};
        int b[] = {1,7,6,0};
        int c[] = {11,3,8,2};
        int k;
        int i,j;
        for(i=0;i<MAX;i++)
                sum_array[i].result=-1;
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        sum_array[a[i]+b[j]].result=a[i]+b[j];
                        sum_array[a[i]+b[j]].i=i;
                        sum_array[a[i]+b[j]].j=j;
                }
        }
        for(k=0;k<n;k++)
        {
                if(sum_array[c[k]].result==c[k])
                {
                        printf("<i,j,k> = <%d,%d,%d>\n",sum_array[c[k]].i,sum_array[c[k]].j,k);
                }
        }
        return 0;
}

My question is how to do it faster ? Any O(N*logN) or better algorithm for this ?

Regards,
Arka

I have already tried with sorting.Can you elaborate please ?

Find out all possible (i,j,k) such that A[i]+B[j]=C[k].

You haven't succeeded in this at all.

You algorithm overrides values so that only one possible match for each `C[K]' is logged.

Any O(N*logN) or better algorithm for this ?

You can get better than "O(n*log(n))" without assuming weird constraints which are probably not intended.

I have already tried with sorting.Can you elaborate please ?

Show us your version that is based on sorting and searching.

Soma

Thanks all of you for replying.

Originally Posted by oogabooga

You haven't succeeded in this at all.

You algorithm overrides values so that only one possible match for each `C[K]' is logged.

I can use chaining to overcome this.Can any one please give me some insight for doing it faster than O(N^2).

Ok fine.Let me take back my solution as if I have not written the above code.Now can anyone please suggest me how to do the same faster than O(N2) ?

You've already been given a hint about doing it with less complexity which you've said you already tried and then denied my request for that solution.

The thing you aren't getting: we aren't here to do your job.

We all have our own problems. We will be happy to help, but that's pretty much the extent of what we will offer.

If you want to do this "faster" post a solution that is correct so that we can appreciate that you understand the problem correctly and knowing that can guide you into improving it by sorting the data.

You may instead post your broken attempt at a sorting based solution and we can guide you to understanding what you did wrong.

I guess you might catch someone in an extremely good mood to post a complete solution for you, but that is unlikely so actually doing one of the two things above is basically a requirement.

Soma

Peoples are upset over here it seems.I didn't mean that and sorry for that.So let's get back to the topic if everything is cool

@phantomotap

Show us your version that is based on sorting and searching.

First I tried to store A[i]+B[j] for all 0<=(i,j)<=n the in an array and then radix sort it and screwed up cause that array itself become of size O(N2).

For the first mistake that for scenario like

Code:

A[]={1,2,0},B[]={3,2,7}

where different (i,j) combination producing same sum for this case A[0]+B[0] and A[1]+B[1] I will use chaining or probing with some handy hash function.

Now can anyone suggest me something from this point ??

Looking forward.....................
Seriously.............

Were you there when I written the code and posted ????
Trust me pal that is mine.....
And I got to tell you, you are not at all helping and it thanks for your kind information that Merge Sort takes O(n*log(n)) ................