**Task Score**

**Correctness**

**Performance**

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

*not defined yet*

**Passed**

```
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function sortAsc(a, b) {
return (a - b)
}
function solution(A) {
let counter = 0
let j= 0;
let leftLimit = [];
let rightLimit = []
//fill the left and right limits of each circle
for(var i=0; i < A.length; i++) {
leftLimit[i] =i-A[i];
rightLimit[i] =i+A[i];
}
console.log(leftLimit)
console.log(rightLimit)
//sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while in the right we will have where the next circle closes
leftLimit.sort(sortAsc)
rightLimit.sort(sortAsc)
console.log(leftLimit)
console.log(rightLimit)
//loop through all the elements of the RIGHT boundaries
for(var i= 0; i<A.length; i++) {
//this is the tricky part to understand
//on the left we have the boundaries of open circles, on the right the boundary of the next circle
//as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
while(j < A.length && rightLimit[i] >= leftLimit[j]){
//we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there
//if j surpasses j, it means we overcalculated and we start to decrease the number of intersections
counter += j-i;
//pass to the next open circle
j++;
}
if(counter > 10000000) return -1;
}
return counter;
}
```

**Example tests**

**OK**

[ -1, -4, 0, 2, 0, 5 ] [ 1, 6, 4, 4, 8, 5 ] [ -4, -1, 0, 0, 2, 5 ] [ 1, 4, 4, 5, 6, 8 ]

```
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function sortAsc(a, b) {
return (a - b)
}
function solution(A) {
let counter = 0
let j= 0;
let leftLimit = [];
let rightLimit = []
//fill the left and right limits of each circle
for(var i=0; i < A.length; i++) {
leftLimit[i] =i-A[i];
rightLimit[i] =i+A[i];
}
console.log(rightLimit)
//sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while in the right we will have where the next circle closes
leftLimit.sort(sortAsc)
rightLimit.sort(sortAsc)
console.log(leftLimit)
console.log(rightLimit)
//loop through all the elements of the RIGHT boundaries
for(var i= 0; i<A.length; i++) {
//this is the tricky part to understand
//on the left we have the boundaries of open circles, on the right the boundary of the next circle
//as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
while(j < A.length && rightLimit[i] >= leftLimit[j]){
//we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there
//if j surpasses j, it means we overcalculated and we start to decrease the number of intersections
counter += j-i;
//pass to the next open circle
j++;
}
if(counter > 10000000) return -1;
}
return counter;
}
```

**Passed**

```
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function sortAsc(a, b) {
return (a - b)
}
function solution(A) {
let counter = 0
let j= 0;
let leftLimit = [];
let rightLimit = []
//fill the left and right limits of each circle
for(var i=0; i < A.length; i++) {
leftLimit[i] =i-A[i];
rightLimit[i] =i+A[i];
}
//sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while in the right we will have where the next circle closes
leftLimit.sort(sortAsc)
rightLimit.sort(sortAsc)
//loop through all the elements of the RIGHT boundaries
for(var i= 0; i<A.length; i++) {
//this is the tricky part to understand
//on the left we have the boundaries of open circles, on the right the boundary of the next circle
//as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
while(j < A.length && rightLimit[i] >= leftLimit[j]){
//we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there
//if j surpasses j, it means we overcalculated and we start to decrease the number of intersections
counter += j-i;
//pass to the next open circle
j++;
}
if(counter > 10000000) return -1;
}
return counter;
}
```

**Passed**

```
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function sortAsc(a, b) {
return (a - b)
}
function solution(A) {
let counter = 0
let j= 0;
let leftLimit = [];
let rightLimit = []
//fill the left and right limits of each circle
for(var i=0; i < A.length; i++) {
leftLimit[i] =i-A[i];
rightLimit[i] =i+A[i];
}
//sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while in the right we will have where the next circle closes
leftLimit.sort(sortAsc)
rightLimit.sort(sortAsc)
//loop through all the elements of the RIGHT boundaries
for(var i= 0; i<A.length; i++) {
//this is the tricky part to understand
//on the left we have the boundaries of open circles, on the right the boundary of the next circle
//as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
while(j < A.length && rightLimit[i] >= leftLimit[j]){
//we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there
//if j surpasses j, it means we overcalculated and we start to decrease the number of intersections
counter += j-i;
//pass to the next open circle
j++;
}
if(counter > 10000000) return -1;
}
return counter;
}
```

**100**

```
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function sortAsc(a, b) {
return (a - b)
}
function solution(A) {
let counter = 0
let j= 0;
let leftLimit = [];
let rightLimit = []
//fill the left and right limits of each circle
for(var i=0; i < A.length; i++) {
leftLimit[i] =i-A[i];
rightLimit[i] =i+A[i];
}
//sort them in an ascending order - why ? Basically we will rearrange their limits in an ascending way, we will have in leftLimit all open circles while in the right we will have where the next circle closes
leftLimit.sort(sortAsc)
rightLimit.sort(sortAsc)
//loop through all the elements of the RIGHT boundaries
for(var i= 0; i<A.length; i++) {
//this is the tricky part to understand
//on the left we have the boundaries of open circles, on the right the boundary of the next circle
//as long as there are circles open (rightLimit[i] >= leftLimit[j]) and (j < A.length)
while(j < A.length && rightLimit[i] >= leftLimit[j]){
//we have circles at each position, so, as long as the left boundaries are smaller or equal to the right boundary, there are circles intersecting there
//if j surpasses j, it means we overcalculated and we start to decrease the number of intersections
counter += j-i;
//pass to the next open circle
j++;
}
if(counter > 10000000) return -1;
}
return counter;
}
```

The solution obtained perfect score.

**O(N*log(N)) or O(N)**

**Correctness tests**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**Performance tests**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**