Tasks Details
medium
Compute the number of intersections in a sequence of discs.
Task Score
56%
Correctness
87%
Performance
25%
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:
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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 22 minutes
Notes
not defined yet
Task timeline
Code: 13:52:06 UTC,
java,
autosave
Code: 13:52:34 UTC,
java,
autosave
// 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");
class Solution {
class circle{
int right;
int left;
circle{
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Code: 13:52:37 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class circle{
int right;
int left;
circle(){
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Analysis
Compile error
Solution.java:17: error: missing return statement
}
^
1 error
Code: 13:52:57 UTC,
java,
autosave
// 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");
class Solution {
class circle{
int right;
int left;
circle(int x, int y){
right = x;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Code: 13:53:07 UTC,
java,
autosave
// 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");
class Solution {
class circle{
int right;
int left;
circle(int center,){
right = x;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Code: 13:53:34 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class circle{
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Analysis
Compile error
Solution.java:18: error: missing return statement
}
^
1 error
Code: 13:53:37 UTC,
java,
autosave
// 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");
class Solution {
class circle{
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
}
}
Code: 13:53:43 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class circle{
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 0 expected 11
Code: 13:57:39 UTC,
java,
autosave
// 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");
class Solution {
class circle {
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:57:56 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:58:14 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Employee o) {
return this.name.compareTo(o.name);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
출처: https://jeong-pro.tistory.com/173 [기본기를 쌓는 정아마추어 코딩블로그]
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:58:26 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
return this.name.compareTo(o.name);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:58:36 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
return this.left.compareTo(o.left);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:11: error: invalid method declaration; return type required
circle(int pos, int length){
^
1 error
Code: 13:58:45 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
return this.left.compareTo(o.left);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:16: error: cannot find symbol
public int Circle(Employee o) {
^
symbol: class Employee
location: class Solution.Circle
Solution.java:8: error: Solution.Circle is not abstract and does not override abstract method compareTo(Solution.Circle) in Comparable
class Circle implements Comparable<Circle> {
^
Solution.java:15: error: method does not override or implement a method from a supertype
@Override
^
Solution.java:17: error: int cannot be dereferenced
return this.left.compareTo(o.left);
^
4 errors
Code: 13:59:07 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
return this.left.compareTo(o.left);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:59:33 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
return 0;
}
return this.left.compareTo(o.left);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 13:59:49 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right)
}
return this.left.compareTo(o.left);
//return this.id - o.id;
//return this.department.compareTo(o.department);
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 14:00:19 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 14:00:20 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Employee o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:16: error: cannot find symbol
public int Circle(Employee o) {
^
symbol: class Employee
location: class Solution.Circle
Solution.java:8: error: Solution.Circle is not abstract and does not override abstract method compareTo(Solution.Circle) in Comparable
class Circle implements Comparable<Circle> {
^
Solution.java:15: error: method does not override or implement a method from a supertype
@Override
^
3 errors
Code: 14:00:28 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int Circle(Circle o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:8: error: Solution.Circle is not abstract and does not override abstract method compareTo(Solution.Circle) in Comparable
class Circle implements Comparable<Circle> {
^
Solution.java:15: error: method does not override or implement a method from a supertype
@Override
^
2 errors
Code: 14:00:41 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
int Circle(Circle o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:8: error: Solution.Circle is not abstract and does not override abstract method compareTo(Solution.Circle) in Comparable
class Circle implements Comparable<Circle> {
^
Solution.java:15: error: method does not override or implement a method from a supertype
@Override
^
2 errors
Code: 14:00:59 UTC,
java,
autosave
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
int Circle(Circle o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 14:01:01 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
int Circle(Circle o) {
if(this.left > o.left){
return 1;
} else if(this.left == o.left){
if(this.right> o.right){
return 1;
}else if(this.right == o.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
Compile error
Solution.java:8: error: Solution.Circle is not abstract and does not override abstract method compareTo(Solution.Circle) in Comparable
class Circle implements Comparable<Circle> {
^
Solution.java:17: error: method does not override or implement a method from a supertype
@Override
^
2 errors
Code: 14:03:43 UTC,
java,
autosave
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
if(this.right> circle.right){
return 1;
}else if(this.right == circle.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Code: 14:03:44 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
if(this.right> circle.right){
return 1;
}else if(this.right == circle.right){
return 0;
}else{
return -1;
}
} else{
return -1;
}
}
}
public int solution(int[] A) {
// write your code in Java SE 8
return 0;
}
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 0 expected 11
Code: 14:13:07 UTC,
java,
autosave
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
return Integer.compare(this.right, circle.right);
} else{
return -1;
}
}
}
public int solution(int[] A) {
int cnt = 0;
Circle[] circleList = new Circle[A.length];
for (int i = 0; i < A.length; i++) {
circleList[i] = (new Circle(i, A[i]));
}
Arrays.sort(circleList);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
if(circleList[i].right >= circleList[j].left){
cnt++;
}
}
}
return cnt;
}
}
Code: 14:13:08 UTC,
java,
verify,
result: Failed
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
return Integer.compare(this.right, circle.right);
} else{
return -1;
}
}
}
public int solution(int[] A) {
int cnt = 0;
Circle[] circleList = new Circle[A.length];
for (int i = 0; i < A.length; i++) {
circleList[i] = (new Circle(i, A[i]));
}
Arrays.sort(circleList);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
if(circleList[i].right >= circleList[j].left){
cnt++;
}
}
}
return cnt;
}
}
Analysis
Compile error
Solution.java:35: error: cannot find symbol
Arrays.sort(circleList);
^
symbol: variable Arrays
location: class Solution
1 error
Code: 14:13:19 UTC,
java,
verify,
result: Passed
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
return Integer.compare(this.right, circle.right);
} else{
return -1;
}
}
}
public int solution(int[] A) {
int cnt = 0;
Circle[] circleList = new Circle[A.length];
for (int i = 0; i < A.length; i++) {
circleList[i] = (new Circle(i, A[i]));
}
Arrays.sort(circleList);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
if(circleList[i].right >= circleList[j].left){
cnt++;
}
}
}
return cnt;
}
}
Analysis
Code: 14:13:26 UTC,
java,
verify,
result: Passed
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
return Integer.compare(this.right, circle.right);
} else{
return -1;
}
}
}
public int solution(int[] A) {
int cnt = 0;
Circle[] circleList = new Circle[A.length];
for (int i = 0; i < A.length; i++) {
circleList[i] = (new Circle(i, A[i]));
}
Arrays.sort(circleList);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
if(circleList[i].right >= circleList[j].left){
cnt++;
}
}
}
return cnt;
}
}
Analysis
Code: 14:13:30 UTC,
java,
final,
score:
56
// 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");
class Solution {
static class Circle implements Comparable<Circle> {
int right;
int left;
Circle(int pos, int length){
right = pos + length;
left = pos - length;
}
@Override
public int compareTo(Circle circle) {
if(this.left > circle.left){
return 1;
} else if(this.left == circle.left){
return Integer.compare(this.right, circle.right);
} else{
return -1;
}
}
}
public int solution(int[] A) {
int cnt = 0;
Circle[] circleList = new Circle[A.length];
for (int i = 0; i < A.length; i++) {
circleList[i] = (new Circle(i, A[i]));
}
Arrays.sort(circleList);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
if(circleList[i].right >= circleList[j].left){
cnt++;
}
}
}
return cnt;
}
}
Analysis summary
The following issues have been detected: wrong answers, timeout errors.
For example, for the input [1, 2147483647, 0] the solution returned a wrong answer (got 0 expected 2).
Analysis
Detected time complexity:
O(N**2)
expand all
Correctness tests
1.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
1.
0.004 s
OK
1.
0.004 s
WRONG ANSWER,
got 0 expected 2
2.
0.004 s
OK
expand all
Performance tests
1.
0.020 s
OK
1.
0.052 s
OK
1.
0.264 s
TIMEOUT ERROR,
running time: 0.264 sec., time limit: 0.100 sec.
1.
0.996 s
TIMEOUT ERROR,
running time: 0.996 sec., time limit: 0.128 sec.
10M_intersections
10.000.000 intersections
10.000.000 intersections
✘
TIMEOUT ERROR
running time: 0.884 sec., time limit: 0.100 sec.
running time: 0.884 sec., time limit: 0.100 sec.
1.
0.884 s
TIMEOUT ERROR,
running time: 0.884 sec., time limit: 0.100 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
0.004 s
OK
1.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
2.
0.004 s
OK
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
0.008 s
OK