Tasks Details
medium
Compute the number of intersections in a sequence of discs.
Task Score
100%
Correctness
100%
Performance
100%
We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
The figure below shows discs drawn for N = 6 and A as follows:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0
There are eleven (unordered) pairs of discs that intersect, namely:
- discs 1 and 4 intersect, and both intersect with all the other discs;
- disc 2 also intersects with discs 0 and 3.
Write a function:
function solution(A);
that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Given array A shown above, the function should return 11, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..2,147,483,647].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used JavaScript
Time spent on task 3 minutes
Notes
not defined yet
Code: 16:35:17 UTC,
java,
autosave
Code: 16:35:24 UTC,
js,
autosave
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i)=> Object({L: i - v, R: i + v}));
return discs.sort((a,b)=>a.L-b.L).reduce((acc,v,i)=>{
for(let j=i+1, len = A.length; j<len; j++){
if(v.R < discs[j].L) break;
else acc++;
}
if(acc > 10000000) return discs.splice(1) && -1;
return acc;
},0);
}
Code: 16:36:17 UTC,
js,
autosave
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i)=> Object({L: i - v, R: i + v}));
return discs.sort((a,b)=>a.L-b.L).reduce((acc,v,i)=>{
for(let j=i+1, len = A.length; j<len; j++){
if(v.R < discs[j].L) break;
else acc++;
}
return discs.splice(1) && -1;
return acc;
},0);
}
Code: 16:36:28 UTC,
js,
verify,
result: Passed
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i)=> Object({L: i - v, R: i + v}));
return discs.sort((a,b)=>a.L-b.L).reduce((acc,v,i)=>{
for(let j=i+1, len = A.length; j<len; j++){
if(v.R < discs[j].L) break;
else acc++;
}
return acc > 10000000 ? discs.splice(1) && -1 : acc;
},0);
}
Analysis
Code: 16:37:00 UTC,
js,
autosave
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i)=> Object({L: i - v, R: i + v}));
return discs.sort((a, b) => a.L - b.L).reduce((acc, v, i) => {
for (let j = i + 1, len = A.length; j < len; j++) {
if (v.R < discs[j].L) break;
else acc++;
}
return acc > 10000000 ? discs.splice(1) && -1 : acc;
}, 0);
}
Code: 16:37:13 UTC,
js,
verify,
result: Passed
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i) => Object({L: i - v, R: i + v}));
return discs.sort((a, b) => a.L - b.L).reduce((acc, v, i) => {
for (let j = i + 1, len = A.length; j < len; j++) {
if (v.R < discs[j].L) break;
else acc++;
}
return acc > 10000000 ? discs.splice(1) && -1 : acc;
}, 0);
}
Analysis
Code: 16:37:21 UTC,
js,
verify,
result: Passed
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i) => Object({L: i - v, R: i + v}));
return discs.sort((a, b) => a.L - b.L).reduce((acc, v, i) => {
for (let j = i + 1, len = A.length; j < len; j++) {
if (v.R < discs[j].L) break;
else acc++;
}
return acc > 10000000 ? discs.splice(1) && -1 : acc;
}, 0);
}
Analysis
Code: 16:37:23 UTC,
js,
final,
score:
100
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
const discs = A.map((v,i) => Object({L: i - v, R: i + v}));
return discs.sort((a, b) => a.L - b.L).reduce((acc, v, i) => {
for (let j = i + 1, len = A.length; j < len; j++) {
if (v.R < discs[j].L) break;
else acc++;
}
return acc > 10000000 ? discs.splice(1) && -1 : acc;
}, 0);
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
1.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
1.
0.072 s
OK
1.
0.072 s
OK
1.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
expand all
Performance tests
1.
0.080 s
OK
1.
0.092 s
OK
1.
0.104 s
OK
1.
0.136 s
OK
1.
0.148 s
OK
1.
0.216 s
OK
2.
0.072 s
OK
1.
0.384 s
OK
2.
0.072 s
OK
1.
0.308 s
OK
2.
0.072 s
OK