Tasks Details
medium
Given a set of points on a plane, find the largest number of points that can be enclosed within a circle centered on the origin, such that the number of red points and green points inside it is equal.
Task Score
100%
Correctness
100%
Performance
100%
There are N points (numbered from 0 to N−1) on a plane. Each point is colored either red ('R') or green ('G'). The K-th point is located at coordinates (X[K], Y[K]) and its color is colors[K]. No point lies on coordinates (0, 0).
We want to draw a circle centered on coordinates (0, 0), such that the number of red points and green points inside the circle is equal. What is the maximum number of points that can lie inside such a circle? Note that it is always possible to draw a circle with no points inside.
Write a function:
class Solution { public int solution(int[] X, int[] Y, String colors); }
that, given two arrays of integers X, Y and a string colors, returns an integer specifying the maximum number of points inside a circle containing an equal number of red points and green points.
Examples:
1. Given X = [4, 0, 2, −2], Y = [4, 1, 2, −3] and colors = "RGRR", your function should return 2. The circle contains points (0, 1) and (2, 2), but not points (−2, −3) and (4, 4).
2. Given X = [1, 1, −1, −1], Y = [1, −1, 1, −1] and colors = "RGRG", your function should return 4. All points lie inside the circle.
3. Given X = [1, 0, 0], Y = [0, 1, −1] and colors = "GGR", your function should return 0. Any circle that contains more than zero points has an unequal number of green and red points.
4. Given X = [5, −5, 5], Y = [1, −1, −3] and colors = "GRG", your function should return 2.
5. Given X = [3000, −3000, 4100, −4100, −3000], Y = [5000, −5000, 4100, −4100, 5000] and colors = "RRGRG", your function should return 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of arrays X and Y is an integer within the range [−20,000..20,000];
- string colors is made only of the characters 'R' and/or 'G';
- no point lies on the coordinates (0, 0).
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 11
Time spent on task 51 minutes
Notes
not defined yet
Code: 02:23:33 UTC,
java,
autosave
Code: 02:50:46 UTC,
java11,
autosave
Code: 03:13:36 UTC,
java11,
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 {
public int solution(int[] X, int[] Y, String colors) {
// Make Tree map with key of square of lengths and color value
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 0; i < X.length; i++) {
int p = X[i] * X[i] + Y[i] * Y[i];
map.put(p, map.getOrDefault(p, "") + colors.charAt(i));
}
final AtomicInteger res = new AtomicInteger();
final AtomicInteger R = new AtomicInteger();
final AtomicInteger G = new AtomicInteger();
map.forEach((integer, s) -> {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') {
R.incrementAndGet();
} else {
G.incrementAndGet();
}
}
final int r = R.get();
if (r == G.get()) {
res.set(r * 2);
}
});
return res.get();
}
}
Code: 03:13:47 UTC,
java11,
autosave
// you can also use imports, for example:
// import java.util.*;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] X, int[] Y, String colors) {
// Make Tree map with key of square of lengths and color value
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 0; i < X.length; i++) {
int p = X[i] * X[i] + Y[i] * Y[i];
map.put(p, map.getOrDefault(p, "") + colors.charAt(i));
}
final AtomicInteger res = new AtomicInteger();
final AtomicInteger R = new AtomicInteger();
final AtomicInteger G = new AtomicInteger();
map.forEach((integer, s) -> {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') {
R.incrementAndGet();
} else {
G.incrementAndGet();
}
}
final int r = R.get();
if (r == G.get()) {
res.set(r * 2);
}
});
return res.get();
}
}
Code: 03:13:48 UTC,
java11,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] X, int[] Y, String colors) {
// Make Tree map with key of square of lengths and color value
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 0; i < X.length; i++) {
int p = X[i] * X[i] + Y[i] * Y[i];
map.put(p, map.getOrDefault(p, "") + colors.charAt(i));
}
final AtomicInteger res = new AtomicInteger();
final AtomicInteger R = new AtomicInteger();
final AtomicInteger G = new AtomicInteger();
map.forEach((integer, s) -> {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') {
R.incrementAndGet();
} else {
G.incrementAndGet();
}
}
final int r = R.get();
if (r == G.get()) {
res.set(r * 2);
}
});
return res.get();
}
}
Code: 03:14:10 UTC,
java11,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] X, int[] Y, String colors) {
// Make Tree map with key of square of lengths and color value
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 0; i < X.length; i++) {
int p = X[i] * X[i] + Y[i] * Y[i];
map.put(p, map.getOrDefault(p, "") + colors.charAt(i));
}
final AtomicInteger res = new AtomicInteger();
final AtomicInteger R = new AtomicInteger();
final AtomicInteger G = new AtomicInteger();
map.forEach((integer, s) -> {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') {
R.incrementAndGet();
} else {
G.incrementAndGet();
}
}
final int r = R.get();
if (r == G.get()) {
res.set(r * 2);
}
});
return res.get();
}
}
Code: 03:14:17 UTC,
java11,
final,
score:
100
// you can also use imports, for example:
// import java.util.*;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] X, int[] Y, String colors) {
// Make Tree map with key of square of lengths and color value
TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 0; i < X.length; i++) {
int p = X[i] * X[i] + Y[i] * Y[i];
map.put(p, map.getOrDefault(p, "") + colors.charAt(i));
}
final AtomicInteger res = new AtomicInteger();
final AtomicInteger R = new AtomicInteger();
final AtomicInteger G = new AtomicInteger();
map.forEach((integer, s) -> {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'R') {
R.incrementAndGet();
} else {
G.incrementAndGet();
}
}
final int r = R.get();
if (r == G.get()) {
res.set(r * 2);
}
});
return res.get();
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Correctness tests
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
1.
0.056 s
OK
2.
0.052 s
OK
3.
0.056 s
OK
4.
0.056 s
OK
5.
0.056 s
OK
6.
0.056 s
OK
1.
0.052 s
OK
2.
0.052 s
OK
3.
0.056 s
OK
4.
0.056 s
OK
5.
0.056 s
OK
small_different_distances
Small tests where all points have distinct distances from the origin. N <= 50.
Small tests where all points have distinct distances from the origin. N <= 50.
✔
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.060 s
OK
5.
0.056 s
OK
small_imbalanced
Small tests where the proportion of color occurences is imbalanced. N <= 50.
Small tests where the proportion of color occurences is imbalanced. N <= 50.
✔
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.056 s
OK
5.
0.052 s
OK
1.
0.056 s
OK
2.
0.052 s
OK
3.
0.056 s
OK
4.
0.056 s
OK
5.
0.056 s
OK
small_sorted
Small tests where points are given in increasing order of distance from (0, 0). N <= 50.
Small tests where points are given in increasing order of distance from (0, 0). N <= 50.
✔
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.056 s
OK
5.
0.056 s
OK
6.
0.056 s
OK
7.
0.056 s
OK
8.
0.056 s
OK
expand all
Correctness/performance tests
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.068 s
OK
5.
0.060 s
OK
6.
0.060 s
OK
7.
0.060 s
OK
8.
0.056 s
OK
expand all
Performance tests
1.
3.180 s
OK
2.
3.492 s
OK
3.
3.388 s
OK
1.
3.216 s
OK
2.
3.192 s
OK
3.
3.412 s
OK
1.
2.844 s
OK
2.
2.980 s
OK
3.
2.968 s
OK
4.
3.080 s
OK
1.
1.964 s
OK
2.
2.060 s
OK
3.
2.072 s
OK
1.
3.968 s
OK
2.
4.192 s
OK
3.
4.188 s
OK
4.
4.288 s
OK