Tasks Details
easy
1.
Distinct
Compute number of distinct values in an array.
Task Score
100%
Correctness
100%
Performance
100%
Write a function
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns the number of distinct values in array A.
For example, given array A consisting of six elements such that:
A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
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 [−1,000,000..1,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 17 minutes
Notes
not defined yet
Code: 13:16:42 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = A.length;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : element;
bitSet.set(index);
}
return bitSet.cardinality();
}
}
Analysis
Code: 13:17:24 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = A.length;
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : element;
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
expand all
User tests
1.
1.301 s
OK
function result: 1
function result: 1
1.
1.331 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -1 at java.util.BitSet.set(BitSet.java:444) at Solution.solution(Solution.java:10) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 13:17:48 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = A.length;
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1 );
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:19:06 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 100000;
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1 );
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:19:22 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1000000;
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1 );
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:19:44 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1000000;
BitSet bitSet = new BitSet( (offset * 2) + 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1 );
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:20:20 UTC,
java,
verify,
result: Failed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1e6;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}
Analysis
Compile error
Solution.java:5: error: incompatible types: possible lossy conversion from double to int
int offset = 1e6;
^
1 error
Code: 13:22:23 UTC,
java,
verify,
result: Failed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 10e6;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}
Analysis
Compile error
Solution.java:5: error: incompatible types: possible lossy conversion from double to int
int offset = 10e6;
^
1 error
Code: 13:26:13 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1_000_000;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) - 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:26:54 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1_000_000;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) + 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:27:11 UTC,
java,
verify,
result: Passed
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1_000_000;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) + 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}
User test case 1:
[0]
User test case 2:
[-1, 1, 0, 1]
Analysis
Code: 13:27:19 UTC,
java,
final,
score:
100
import java.util.BitSet;
class Solution {
public int solution(int[] A) {
int offset = 1_000_000;
// first part for negatives, second part for positives and adding
// counting zero as part of the positives section
BitSet bitSet = new BitSet( (offset * 2) + 1 );
for (int element : A ) {
int index = element >= 0 ? offset + element : (element * -1);
bitSet.set(index);
}
return bitSet.cardinality();
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
1.317 s
OK
1.
1.332 s
OK
2.
1.325 s
OK
1.
1.314 s
OK
1.
1.328 s
OK
1.
1.336 s
OK
1.
1.326 s
OK
1.
1.325 s
OK
1.
1.327 s
OK
1.
1.188 s
OK