1. ## 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(N2).Following is the algorithm I wrtten for O(N2)
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

2. Hint: sorting.

4. 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.

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

Soma

5. As phantomotap has indicated, you've put a rather bizarre restriction on the maximum sum. Is that allowed in the specs? Moreover, you aren't even getting the right answer. Implement the naive O(N cubed) algorithm so that you at least know what the correct answer is.

6. 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).

7. As stated above, your ORIGINAL IMPLEMENTATION IS WRONG. Fix it, and provide a less efficient but CORRECT solution and then we can improve the complexity. A merge-sort for example, would only take O(n*log(n)).

8. 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) ?

9. 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

10. Originally Posted by arka.sharma
Let me take back my solution
Originally Posted by arka.sharma
I have not written the above code.
I lolled.

Quzah.

11. 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.............

12. Lame bump to a lame thread which contains lame code which is not even yours. What are we talking about? Before you produce any code that is your own, there won't be much help here.

13. 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)) ................

14. You said it yourself!!! You said your self that you have not written the code, I think due to the age of this thread you are tripping yourself in your own myriad of lies. Bottom line is: no code, no help.

15. Originally Posted by claudiu
You said your self that you have not written the code
I don't think he did (my emphasis):
Originally Posted by arka.sharma
Let me take back my solution as if I have not written the above code.