Distinct at app.codility.com/programmers in C++ 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 functionint solution(vector<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] = 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 vector, A is:
vector<int> A{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,
vector<int> A{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 C++ 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 (vector), 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):
#include <iostream>The output is 3. The statement to sort the vector is
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
if (N == 0)
return 0;
int counter = 1; //in case given list has only one element
sort(A.begin(), A.end());
for (int i=0;i<N-1; ++i) {
if (A[i] != A[i+1])
++counter;
}
return counter;
}
int main()
{
vector<int> A{2, 1, 1, 2, 3, 1};
int ret = solution(A);
cout << ret <<endl;
return 0;
}
sort(A.begin(), A.end());
The sort() function takes two arguments: an iterator that points to the first element of the vector and another iteration that points just after the last element of the vector. The sort() function is in the algorithm library, so the algorithm library has to be included.
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 vector 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.
Thanks for reading.