Compute the number of intersections in a sequence of discs.

hey, One of our users asked for the solution to Compute the number of intersections in a sequence of discs, He is preparing for online coding test on Codility test to get a job in MNC. As we short out the problem of our user.

Task description

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

function solution(A) {
    // write your code in JavaScript (Node.js 4.0.0)
    var items = [];
    var intersections = 0;
    const LIMIT = 10000000;
    
    for(var i=0; i<A.length; i++) {
        items.push({
            base: i,
            start: i - A[i],
            end: i + A[i]
        });
    }
    
    items.sort(function(a, b) {
        return a.start - b.start;
    });
    
    var sameStart = 0;
    for(var i=0; i<items.length; i++) {
        var item = items[i];
        var j=i+1;
        
        while(items[j] && item.end >= items[j].start) {
            if(++intersections > LIMIT) return -1;
            
            if(item.start === items[j++].start) {
                sameStart++;
            }
        }
        
        sameStart = 0;
    }
    
    return intersections;
}