Distinct at app.codility.com/programmers in Go Explained: Compute number of distinct values in an array.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)
Lesson 6 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 2 Jul 2025
Problem
Write a functionfunc Solution(A []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] = 1
the 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].
Note
It can be cumbersome to solve this problem the brute force way, so only the smart approach is given.The array, A is:
var A = []int{2, 1, 1, 2, 3, 1};
Smart Approach
This tutorial (lesson) is on sorting, so it should occur to the reader that sorting should be required in the solution. The list is sorted first in ascending order.The given list,
var A = []int{2, 1, 1, 2, 3, 1};
sorted, becomes:
1, 1, 1, 2, 2, 3
After the list has been sorted, elements appear in groups of the same value. The sorted list is then scanned to count each repeated and non-repeated element once.
If the Go predefined sorting function is used, then that sorting function will take a maximum of O(n.log2n) time. The scanning takes an extra n time. So, expected time complexity is O(n.log2n + n) .
In order to count the number of distinct values, in the sorted list (array), two consecutive numbers are compared, beginning from the element at index 0 (zero based indexing). This means that i in the for-loop is incremented (by 1) for each pair until index N-2. The last element is at index N-1 for zero based indexing. This element is compared with the previous element, and i does not reach the last element in the following code.
Since the sorted elements have to be compared in consecutive pairs, what happens if the list has just one element? In this case, 1 is returned because there is only one distinct element. A list of length 1 has only one distinct element by default. If the length of the list is zero, then the number of distinct elements is zero, and zero is returned, as the list has no element. The program is (read the code and comments):
package main
import (
"fmt";
"sort" //for sorting a slice
)
func Solution(A []int) int {
var N int = len(A);
if N == 0 {
return 0;
}
var counter int = 1; //in case given list has only one element
sort.Ints(A);
for i:=0;i<N-1; i++ {
if A[i] != A[i+1] {
counter++;
}
}
return counter;
}
func main() {
var A = []int{2, 1, 1, 2, 3, 1};
var ret int = Solution(A);
fmt.Println(ret);
}
The output is 3. The statement to sort the array issort.Ints(A);
The sort() method is in the Go.util.Arrays library, which has to be imported.
Note that the programmer has not defined his/her own sorting function.
Note that after deciding that the list is not of zero length in the solution() function, the counter is given the value 1, for the case when the length of the list is one. The while-condition in the for-loop is such that, if the length of the array is 1, the for-loop will not execute. In this case, 1 already assigned to the counter, will be returned.
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)
This problem can also be approach as the exercise problem in the lesson (tutorial) was approached. However, here, the case for N = 0, has to be taken into consideration.
Remember that at app.codility.com, the Go main function is not typed (not submitted). Before submitting, also delete '"fmt";' and replace "package main" with "package solution".
Thanks for reading.