# Finding the pairs of intersecting discs

I have been following this question on SO, copied below. I put together a solution, but which is $O(n^2)$. In order to get a more efficient $O(n \log n)$ or $O(\log n)$ solution, I tried to sort that array, but could not get it solved hence would like to ask here how to optimize this solution to get it in less time complexity in C?

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that the k-th disc and j-th disc intersect if they have at least one common point.

Write a function

int number_of_disc_intersections(int[] A);


which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and

A = 1
A = 5
A = 2
A = 1
A = 4
A = 0


there are 11 pairs of intersecting discs:

1. 0th and 1st
2. 0th and 2nd
3. 0th and 4th
4. 1st and 2nd
5. 1st and 3rd
6. 1st and 4th
7. 1st and 5th
8. 2nd and 3rd
9. 2nd and 4th
10. 3rd and 4th
11. 4th and 5th

so the function should return 11. The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

C language solution:

int disc_intersecn(int *A,int N)
{
int i,j,cnt=0;
/*
qsort(A,N,sizeof(A),sort_fn_ascend);
for(i=0;i<(N-1);i++)
{
if(i+A[i] > (i+1-A[i+1]))
{
cnt++;
}
}
*/

for (i = 0; i < N; i++)
{
for (j = i+1; j < N; j++)
{
if (i + A[i] >= j - A[j]) cnt++;
}
}

return cnt;
}

• Seeing as that question already has an answer explaining the method, why are you asking here? – Winston Ewert Jan 29 '12 at 15:50
• @WinstonEwert - Because I am trying to solve it in C , not in C#, Python, Java which are mentioned, and i did not get the explanation. – goldenmean Jan 29 '12 at 16:01
• He's also looking for an improved solution (meaning faster, more efficient). His example solution was simply to illustrate an O(N²) solution. Clearly there is room for improvement if a fancier solution is available. – Todd Lehman Jan 29 '12 at 16:11
• What do you think somebody is going to give you here besides a description of the same algorithm? – Winston Ewert Jan 29 '12 at 18:37
• @ToddLehman, yes. But his link already describes the fancier solution. – Winston Ewert Jan 29 '12 at 18:37