Tasks Details
easy
1.
Distinct
Compute number of distinct values in an array.
Task Score
100%
Correctness
100%
Performance
100%
Write a function
object Solution { def solution(a: Array[Int]): Int }
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 Scala
Time spent on task 7 minutes
Notes
not defined yet
Task timeline
Code: 04:34:34 UTC,
scala,
verify,
result: Failed
object Solution {
def solution(A: Array[Int]): Int = {
val positive = new java.util.BitSet()
val negative = new java.util.BitSet()
A.foldLeft(0)((current, i) =>
(positive get i, negative get i * -1) match {
case (false, false) =>
if (i > 0) positive set i
else negative set i * -1
current + 1
}
)
}
}
Analysis
expand all
Example tests
1.
2.363 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -2 at java.util.BitSet.get(BitSet.java:471) at Solution$$anonfun$solution$1.apply$mcIII$sp(Solution.scala:7) at Solution$$anonfun$solution$1.apply(Solution.scala:6) at Solution$$anonfun$solution$1.apply(Solution.scala:6) at scala.collection.IndexedSeqOptimized$class.foldl(IndexedSeqOptimized.scala:57) at scala.collection.IndexedSeqOptimized$class.foldLeft(IndexedSeqOptimized.scala:66) at scala.collection.mutable.ArrayOps$ofInt.foldLeft(ArrayOps.scala:234) at Solution$.solution(Solution.scala:6) at Wrapper$.run(user.scala:31) at Wrapper$.main(user.scala:24) at Wrapper.main(user.scala)
Code: 04:36:26 UTC,
scala,
verify,
result: Failed
object Solution {
def solution(A: Array[Int]): Int = {
val positive = new java.util.BitSet()
val negative = new java.util.BitSet()
A.foldLeft(0)((current, i) =>
val duplicate = if (i < 0) negative get i * -1
else positive get i
duplicate match {
case true =>
current
case false =>
if (i >= 0) positive set i
else negative set i * -1
current + 1
}
)
}
}
Analysis
Compile error
Solution.scala:7: error: illegal start of simple expression
val duplicate = if (i < 0) negative get i * -1
^
Solution.scala:21: error: ')' expected but '}' found.
}
^
two errors found
Code: 04:37:05 UTC,
scala,
verify,
result: Passed
object Solution {
def solution(A: Array[Int]): Int = {
val positive = new java.util.BitSet()
val negative = new java.util.BitSet()
A.foldLeft(0) { (current, i) =>
val duplicate = if (i < 0) (negative get i * -1)
else (positive get i)
duplicate match {
case true =>
current
case false =>
if (i >= 0) positive set i
else negative set i * -1
current + 1
}
}
}
}
Analysis
Code: 04:38:01 UTC,
scala,
verify,
result: Passed
object Solution {
def solution(A: Array[Int]): Int = {
val positive = new java.util.BitSet()
val negative = new java.util.BitSet()
A.foldLeft(0) { (current, i) =>
val duplicate = if (i < 0) (negative get i * -1)
else (positive get i)
duplicate match {
case true =>
current
case false =>
if (i >= 0) positive set i
else negative set i * -1
current + 1
}
}
}
}
Analysis
Code: 04:38:13 UTC,
scala,
final,
score:
100
object Solution {
def solution(A: Array[Int]): Int = {
val positive = new java.util.BitSet()
val negative = new java.util.BitSet()
A.foldLeft(0) { (current, i) =>
val duplicate = if (i < 0) (negative get i * -1)
else (positive get i)
duplicate match {
case true =>
current
case false =>
if (i >= 0) positive set i
else negative set i * -1
current + 1
}
}
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N) or O(N*log(N))
expand all
Correctness tests
1.
2.428 s
OK
1.
2.389 s
OK
2.
2.448 s
OK
1.
2.467 s
OK
1.
2.416 s
OK
1.
2.409 s
OK
1.
2.406 s
OK
1.
2.386 s
OK
1.
2.370 s
OK
1.
2.379 s
OK