http://www.spoj.com/problems/SUMFOUR/ I am doing this problem. I am getting WA. I dont know the reason why it is so. Here is my code. http://ideone.com/8GTkuF . Please take a look and help me. I am first taking the sum of all elements of array b with each element of array a and similarly I doing that for arrays c & d. Then starting from i=0 I am doing binary search to see whether the element -ab[i] is present in array cd. If i find such a element then I am increasing the count by 1. I have gone through the entire code. Could there be a problem in qsort() inbuilt C library function I am using?
qsort may TLE
qsort() is quicksort which has worst case O(N^2), while STL sort()
is introsort which has worst case O(NlgN)
You can see comparison
wiki link
But I am getting WA not TLE inspite of using qsort(). Please help.
You are looking for only one match in cd for every element in ab. But your code will faulter if there are more than one elements in cd which are equal to -ab[i] for a particular i. For eg. the code gives wrong output for the following test case:
3
0 0 0 0
0 0 0 0
0 0 0 0