# Codility ‘NumberOfDiscIntersections’ 2010 Beta Solution

##### Short Problem Definition:

Compute intersections between sequence of discs.

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.

Number of Disc Intersections

##### Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

##### Execution:

In my mind this problem is very similar to the Codility Fish. You keep count of how many not-yet-ended disks there are. Every beginning has to cross all not-yet-ended disks. The best explanation on the web was written by Luca. His solution is much better than my C-style double-checked while loop. I therefore created a mixture of both 🙂

• Keep in mind that any pair of circles can intersect only once.
• If 1+ beginnings have the same point as 1+ endings. You first have to process the beginnings. The old and new ones have per definition a meeting point.
##### Solution:
```def solution(A):
circle_endpoints = []
for i, a in enumerate(A):
circle_endpoints += [(i-a, True), (i+a, False)]

circle_endpoints.sort(key=lambda x: (x[0], not x[1]))

intersections, active_circles = 0, 0

for _, is_beginning in circle_endpoints:
if is_beginning:
intersections += active_circles
active_circles += 1
else:
active_circles -= 1
if intersections > 10E6:
return -1

return intersections
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• João Prudêncio

Isn’t the time complexity here nlogn + n ?
Since nlogn is for sorting an you also iterate through all the array.

• BruceFromSeattle

I submit 2 solutions (in C#, sorry) which are 100% in agreement and 100% Codility correct; 2nd one is 100% Codility performant.

static int solution(int[] A) // time O(N^2), space O(1)
{ // simple-minded way: check if each (unordered) pair is intersecting
int n = A.Length;
int numIntersecs = 0;
for (long i = 0; i < n – 1; i++)
for (long j = i + 1; j < n; j++)
if (i – A[i] <= j + A[j] && j – A[j] <= i + A[i]) //just touching is intersection
if (numIntersecs == 10E6)
return -1;
else
numIntersecs++;
return numIntersecs;
}
static int solution(int[] A) // time O(N*Log(N)), space O(N)
{ // decrement max number of pairs by number of non-intersecting pairs
long n = A.Length;
if (n < 2)
return 0;
long numIntersecs = n * (n – 1) / 2; // unordered pairs, initialized to max possible
long[] hiVals = new long[n];
long[] loVals = new long[n];
for (long i = 0; i < n; i++)
{
hiVals[i] = i + A[i]; // high value of disk edge (along x-axis)
loVals[i] = i – A[i]; // low value of disk edge (along x-axis)
}
Array.Sort(hiVals);
Array.Sort(loVals);
int jLo = 0; // initialize inner iterator only once
for (int iHi = 0; iHi < n; iHi++)
{
for ( ; jLo hiVals[iHi]) // disks don’t intersect if one’s lo > other’s hi
{
numIntersecs -= n – jLo; // decrement by the num of lo values > this hi value
break; // don’t increment iterator, check this low value again next time
}
}
if (jLo == n)
break; // no more low values > high values
}
if (numIntersecs > 10E6)
return -1;
else
return (int) numIntersecs;
}

• thanks for sharing!

• Pias Kumar Das

Here is my solution.(100/100)

public int solution(int[] A) {
// write your code in Java SE 8
// write your code in Java SE 8
if(A.length<2)
return 0;
Long r[]=new Long[A.length];
Long l[]=new Long[A.length];

for(int i=0;i<A.length;i++)
{
if(A[i]==0)
{
r[i]=l[i]=(long)i;
}
else
{
r[i]=(long)i+A[i];
l[i]=(long)i-A[i];
}
}

Arrays.sort(r);
Arrays.sort(l);

int in=0;
long s=0;

for(int i=0;ir[in])
{
int y=0;
while(inr[in])
{
y++;
in++;
}
if(y>0)
s=s+(l.length-i)*y;
}

}

long t=(((long)A.length)*((long)A.length-1))/2;
//System.out.println(t-s);
if((t-s)>10000000)
return -1;
return (int)(t-s);
}

• Pias Kumar Das

my solution:(100/100)
``` public int solution(int[] A) { // write your code in Java SE 8 // write your code in Java SE 8 if(A.length<2) return 0; Long r[]=new Long[A.length]; Long l[]=new Long[A.length];```

``` for(int i=0;i<A.length;i++) { if(A[i]==0) { r[i]=l[i]=(long)i; } else { r[i]=(long)i+A[i]; l[i]=(long)i-A[i]; } } Arrays.sort(r); Arrays.sort(l); int in=0; long s=0; for(int i=0;ir[in]) { int y=0; while(inr[in]) { y++; in++; } if(y>0) s=s+(l.length-i)*y; } } ```

``` long t=(((long)A.length)*((long)A.length-1))/2; //System.out.println(t-s); if((t-s)>10000000) return -1; return (int)(t-s); } ```

• seems that I managed to fix it…

– besides ``` you also need the block. - the after adding pre, the code coloring kicked in, but it was still messed up. It seems that you need to have a space in between any text and your code block. I did not know that. The code probably needs it's own paragraph...```

• ``` public int solution(int[] A) { // write your code in Java SE 8 // write your code in Java SE 8 if (A.length < 2) return 0; Long r[] = new Long[A.length]; Long l[] = new Long[A.length];```

``` for (int i = 0; i < A.length; i++) { if (A[i] == 0) { r[i] = l[i] = (long) i; } else { r[i] = (long) i + A[i]; l[i] = (long) i - A[i]; } } Arrays.sort(r); Arrays.sort(l); int in = 0; long s = 0; for (int i = 0; i r[in]) { int y = 0; while (in r[in]) { y++; in++; } if (y > 0) s = s + (l.length - i) * y; } } ```

``` long t = (((long) A.length) * ((long) A.length - 1)) / 2; //System.out.println(t-s); if ((t - s) > 10000000) return -1; return (int) (t - s); } ```

• Eduardo

I don’t fully understand codility lesson… For the example (counting duplicates)
Discs that intersect
0 with (1,2,4)
1 with (0,2,3,4,5)
2 with (0,1,3,4)
3 with (1,2,4)
4 with (0,1,2,3,5)
5 with (1,4)
Pairs of discs that intersect (output 11 without duplicates)
(0,1), (0,2), (0,4)
(1,2), (1,3), (1,4), (1,5)
(2,3), (2,4)
(3,4)
(4,5)

But my code failed for input array[1,1,1], codility says that output should be 3 but I only can see 2 following above logic of deleting duplicates
Discs that intersect
0 with (1)
1 with (0,2)
2 with (1)
Pairs of discs that intersect (output 2 without duplicates) > Codility expects 3!
(1,0), (1,2)

Can you give a clue about what I am understanding wrong? Thanks!