Broad Network


Distinct at app.codility.com/programmers in PHP 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 function

    function solution($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 array, A is:

    const 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,

    const 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 PHP array predefined sorting method is used, then that sorting function should 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): 
<?php
function solution($A) {
    $N = count($A);
    
    if ($N == 0)
        return 0;
    
    $counter = 1;    //in case given list has only one element

    sort($A);
    
    for ($i=0; $i < $N-1; ++$i) {    //will not iterate if list has only one element
        if ($A[$i] != $A[$i+1])
            ++$counter;
    }
    
    return $counter;
}

$A = [2, 1, 1, 2, 3, 1];
$ret = solution($A);
echo $ret . "\n";
?>
The output is 3. The statement to sort the vector is

    sort($A);

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)

Thanks for reading.

The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in PHP for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions





Related Links

Basics of PHP with Security Considerations
White Space in PHP
PHP Data Types with Security Considerations
PHP Variables with Security Considerations
PHP Operators with Security Considerations
PHP Control Structures with Security Considerations
PHP String with Security Considerations
PHP Arrays with Security Considerations
PHP Functions with Security Considerations
PHP Return Statement
Exception Handling in PHP
Variable Scope in PHP
Constant in PHP
PHP Classes and Objects
Reference in PHP
PHP Regular Expressions with Security Considerations
Date and Time in PHP with Security Considerations
Files and Directories with Security Considerations in PHP
Writing a PHP Command Line Tool
PHP Core Number Basics and Testing
Validating Input in PHP
PHP Eval Function and Security Risks
PHP Multi-Dimensional Array with Security Consideration
Mathematics Functions for Everybody in PHP
PHP Cheat Sheet and Prevention Explained
More Related Links

Cousins

BACK NEXT

Comments