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] = 0There 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:
class Solution { public int solution(int[] 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].
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
/* for each disc J in A w/ radius A[J], J *must* intersect with the previous A[J] discs
* for disc J and K s.t. J < K, J intersects K iff J + A[J] >= K - A[K]
* problem is when J + A[J] < K
* need a way to know the number of discs prior to a position I that intersect w/ I
* for I = K-A[K] s.t. K-A[K] > 0, I is the remaining number of discs that intersect w/ K
* already know the number of discs prior to position I (which is simply I)
* can calculate the number of discs prior to position I that *don't* intersect w/ I
* if a disc doesn't intersect w/ I, it won't intersect w/ any position after I
*
* set count to zero
* create array num_no_intersect of length N+1 (tracks number of discs before each position
* that don't intersect that position)
* for each disc J in A
* if J - A[J] <= 0
* count += J b/c disc J *must* intersect w/ the previous J discs
* else
* count += A[J] b/c disc J *must* intersect w/ the previous A[J] discs
* count += J - A[J] - num_no_intersect[J-A[J]] b/c there are J-A[J] discs before disc J
* w/ num_no_intersect[J-A[J]] that don't intersect position J-A[J]
* which is *also* the left border of disc J
* num_no_intersect[J+1] += num_no_intersect[J]
* b/c discs that don't intersect position J also won't intersect position J+1
* if J + A[J] + 1 < N (just after disc J's right border)
* increment num_no_intersect[J+A[J]+1] b/c disc J doesn't intersect any discs on or after that
* return count
*/
class Solution {
private static final int TEN_MILLION = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
int N = A.length, count = 0;
int[] num_no_intersect = new int[N+1]; // tracks the number of discs prior to each position that doesn't intersect that position
for (int J = 0; J < N; J++) {
if (J <= A[J]) {
count += J; // b/c disc J must intersect with the previous J discs
}
else {
count += A[J]; // b/c disc J must intersect with the previous A[J] discs
count += J-A[J] - num_no_intersect[J-A[J]]; // add number of discs before J's left border that intersect it
}
if (count > TEN_MILLION)
return -1; // check for exceptional case
num_no_intersect[J+1] += num_no_intersect[J]; // discs b/f position J also won't intersect position J+1
if (A[J] < N && J+A[J]+1 < N) { // check bounds on A[J] to avoid arithmetic overflow
num_no_intersect[J+A[J]+1]++; // disc J will not intersect positions on or after position J+A[J]+1
}
}
return count;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
/* for each disc J in A w/ radius A[J], J *must* intersect with the previous A[J] discs
* for disc J and K s.t. J < K, J intersects K iff J + A[J] >= K - A[K]
* problem is when J + A[J] < K
* need a way to know the number of discs prior to a position I that intersect w/ I
* for I = K-A[K] s.t. K-A[K] > 0, I is the remaining number of discs that intersect w/ K
* already know the number of discs prior to position I (which is simply I)
* can calculate the number of discs prior to position I that *don't* intersect w/ I
* if a disc doesn't intersect w/ I, it won't intersect w/ any position after I
*
* set count to zero
* create array num_no_intersect of length N+1 (tracks number of discs before each position
* that don't intersect that position)
* for each disc J in A
* if J - A[J] <= 0
* count += J b/c disc J *must* intersect w/ the previous J discs
* else
* count += A[J] b/c disc J *must* intersect w/ the previous A[J] discs
* count += J - A[J] - num_no_intersect[J-A[J]] b/c there are J-A[J] discs before disc J
* w/ num_no_intersect[J-A[J]] that don't intersect position J-A[J]
* which is *also* the left border of disc J
* num_no_intersect[J+1] += num_no_intersect[J]
* b/c discs that don't intersect position J also won't intersect position J+1
* if J + A[J] + 1 < N (just after disc J's right border)
* increment num_no_intersect[J+A[J]+1] b/c disc J doesn't intersect any discs on or after that
* return count
*/
class Solution {
private static final int TEN_MILLION = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
int N = A.length, count = 0;
int[] num_no_intersect = new int[N+1]; // tracks the number of discs prior to each position that doesn't intersect that position
for (int J = 0; J < N; J++) {
if (J <= A[J]) {
count += J; // b/c disc J must intersect with the previous J discs
}
else {
count += A[J]; // b/c disc J must intersect with the previous A[J] discs
count += J-A[J] - num_no_intersect[J-A[J]]; // add number of discs before J's left border that intersect it
}
if (count > TEN_MILLION)
return -1; // check for exceptional case
num_no_intersect[J+1] += num_no_intersect[J]; // discs b/f position J also won't intersect position J+1
if (A[J] < N && J+A[J]+1 < N) { // check bounds on A[J] to avoid arithmetic overflow
num_no_intersect[J+A[J]+1]++; // disc J will not intersect positions on or after position J+A[J]+1
}
}
return count;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
/* for each disc J in A w/ radius A[J], J *must* intersect with the previous A[J] discs
* for disc J and K s.t. J < K, J intersects K iff J + A[J] >= K - A[K]
* problem is when J + A[J] < K
* need a way to know the number of discs prior to a position I that intersect w/ I
* for I = K-A[K] s.t. K-A[K] > 0, I is the remaining number of discs that intersect w/ K
* already know the number of discs prior to position I (which is simply I)
* can calculate the number of discs prior to position I that *don't* intersect w/ I
* if a disc doesn't intersect w/ I, it won't intersect w/ any position after I
*
* set count to zero
* create array num_no_intersect of length N+1 (tracks number of discs before each position
* that don't intersect that position)
* for each disc J in A
* if J - A[J] <= 0
* count += J b/c disc J *must* intersect w/ the previous J discs
* else
* count += A[J] b/c disc J *must* intersect w/ the previous A[J] discs
* count += J - A[J] - num_no_intersect[J-A[J]] b/c there are J-A[J] discs before disc J
* w/ num_no_intersect[J-A[J]] that don't intersect position J-A[J]
* which is *also* the left border of disc J
* num_no_intersect[J+1] += num_no_intersect[J]
* b/c discs that don't intersect position J also won't intersect position J+1
* if J + A[J] + 1 < N (just after disc J's right border)
* increment num_no_intersect[J+A[J]+1] b/c disc J doesn't intersect any discs on or after that
* return count
*/
class Solution {
private static final int TEN_MILLION = 10000000;
public int solution(int[] A) {
// write your code in Java SE 8
int N = A.length, count = 0;
int[] num_no_intersect = new int[N+1]; // tracks the number of discs prior to each position that doesn't intersect that position
for (int J = 0; J < N; J++) {
if (J <= A[J]) {
count += J; // b/c disc J must intersect with the previous J discs
}
else {
count += A[J]; // b/c disc J must intersect with the previous A[J] discs
count += J-A[J] - num_no_intersect[J-A[J]]; // add number of discs before J's left border that intersect it
}
if (count > TEN_MILLION)
return -1; // check for exceptional case
num_no_intersect[J+1] += num_no_intersect[J]; // discs b/f position J also won't intersect position J+1
if (A[J] < N && J+A[J]+1 < N) { // check bounds on A[J] to avoid arithmetic overflow
num_no_intersect[J+A[J]+1]++; // disc J will not intersect positions on or after position J+A[J]+1
}
}
return count;
}
}
The solution obtained perfect score.