Tasks Details
easy
Count the number of distinct slices (containing only unique numbers).
Task Score
70%
Correctness
100%
Performance
40%
An integer M and a non-empty array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.
For example, consider integer M = 6 and array A such that:
A[0] = 3 A[1] = 4 A[2] = 5 A[3] = 5 A[4] = 2There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4).
The goal is to calculate the number of distinct slices.
Write a function:
class Solution { public int solution(int M, int[] A); }
that, given an integer M and a non-empty array A consisting of N integers, returns the number of distinct slices.
If the number of distinct slices is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given integer M = 6 and array A such that:
A[0] = 3 A[1] = 4 A[2] = 5 A[3] = 5 A[4] = 2the function should return 9, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..M].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 52 minutes
Notes
not defined yet
Code: 05:18:58 UTC,
java,
autosave
Code: 06:09:58 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 {
public int solution(int M, int[] A) {
if (M == 0) {
return A.length;
}
// 유니크 여부 판단할 hashset. 정렬 필요없이 검색만.
HashSet<Integer> hSet = new HashSet<>();
int distinctSliceCnt = 0;
for (int i=0; i<A.length; i++) {
hSet.add(A[i]);
distinctSliceCnt++;
for (int j=i+1; j<A.length; j++) {
if (hSet.contains(A[j])) {
break;
} else {
hSet.add(A[j]);
}
distinctSliceCnt++;
}
hSet.clear();
}
return distinctSliceCnt > 1000000000 ? 1000000000 : distinctSliceCnt;
}
}
Code: 06:10:08 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int M, int[] A) {
if (M == 0) {
return A.length;
}
// 유니크 여부 판단할 hashset. 정렬 필요없이 검색만.
HashSet<Integer> hSet = new HashSet<>();
int distinctSliceCnt = 0;
for (int i=0; i<A.length; i++) {
hSet.add(A[i]);
distinctSliceCnt++;
for (int j=i+1; j<A.length; j++) {
if (hSet.contains(A[j])) {
break;
} else {
hSet.add(A[j]);
}
distinctSliceCnt++;
}
hSet.clear();
}
return distinctSliceCnt > 1000000000 ? 1000000000 : distinctSliceCnt;
}
}
Code: 06:10:27 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int M, int[] A) {
if (M == 0) {
return A.length;
}
// 유니크 여부 판단할 hashset. 정렬 필요없이 검색만.
HashSet<Integer> hSet = new HashSet<>();
int distinctSliceCnt = 0;
for (int i=0; i<A.length; i++) {
hSet.add(A[i]);
distinctSliceCnt++;
for (int j=i+1; j<A.length; j++) {
if (hSet.contains(A[j])) {
break;
} else {
hSet.add(A[j]);
}
distinctSliceCnt++;
}
hSet.clear();
}
return distinctSliceCnt > 1000000000 ? 1000000000 : distinctSliceCnt;
}
}
User test case 1:
[8, [0, 5, 3, 8, 7, 3, 0, 4, 0]]
Analysis
Code: 06:10:33 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int M, int[] A) {
if (M == 0) {
return A.length;
}
// 유니크 여부 판단할 hashset. 정렬 필요없이 검색만.
HashSet<Integer> hSet = new HashSet<>();
int distinctSliceCnt = 0;
for (int i=0; i<A.length; i++) {
hSet.add(A[i]);
distinctSliceCnt++;
for (int j=i+1; j<A.length; j++) {
if (hSet.contains(A[j])) {
break;
} else {
hSet.add(A[j]);
}
distinctSliceCnt++;
}
hSet.clear();
}
return distinctSliceCnt > 1000000000 ? 1000000000 : distinctSliceCnt;
}
}
User test case 1:
[8, [0, 5, 3, 8, 7, 3, 0, 4, 0]]
Analysis
Code: 06:10:37 UTC,
java,
final,
score:
70
// you can also use imports, for example:
// import java.util.*;
import java.util.HashSet;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int M, int[] A) {
if (M == 0) {
return A.length;
}
// 유니크 여부 판단할 hashset. 정렬 필요없이 검색만.
HashSet<Integer> hSet = new HashSet<>();
int distinctSliceCnt = 0;
for (int i=0; i<A.length; i++) {
hSet.add(A[i]);
distinctSliceCnt++;
for (int j=i+1; j<A.length; j++) {
if (hSet.contains(A[j])) {
break;
} else {
hSet.add(A[j]);
}
distinctSliceCnt++;
}
hSet.clear();
}
return distinctSliceCnt > 1000000000 ? 1000000000 : distinctSliceCnt;
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N * (N + M))
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
expand all
Performance tests
1.
0.032 s
OK
large
large tests, length = ~100,000
large tests, length = ~100,000
✘
TIMEOUT ERROR
running time: 1.732 sec., time limit: 0.640 sec.
running time: 1.732 sec., time limit: 0.640 sec.
1.
1.732 s
TIMEOUT ERROR,
running time: 1.732 sec., time limit: 0.640 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
large_range
large range tests, length = ~100,000
large range tests, length = ~100,000
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
large_random
large random tests, length = ~100,000
large random tests, length = ~100,000
✘
TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.
Killed. Hard limit reached: 7.000 sec.
1.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
2.
0.676 s
OK
1.
0.388 s
OK
2.
0.580 s
OK