Factor Hackerrank Solution - Using Algorithms Only

Question

I am learning to program and I am doing the hackerrank algorithm exercises. I am in the migratory exercise Birds.

To access the exercise you need login access. As many do not have access, I will copy and paste the exercise here:

You have been Asked to help Study the Population of Birds migrating Across the Continent. Each type of Bird you are interested in will be identified by an integer value. Each time a particular Kind of Bird is Spotted, its id number will be Added to your array of sightings. You would like to be Able to find out which type of Bird is Most common Given a list of sightings.If two or more types of Birds are equally common, Choose the type with the smallest ID number.

Function Description

Complete the migratoryBirds Function in the editor Below. It has two Parameters:

Integer, , denoting the number of Elements in the input array. Integer Array, with array Elements denoting the respective type Numbers of each Bird in the Flock. The Function must Return an integer denoting the type number of the Most common Bird.

Raw Input Format

The first line contains an integer denoting n, the number of Birds sighted and reported in the array . The Second line describes ar as n space-separated integers Representing the type Numbers of each Bird sighted.

Personal,

my solution is this:

function migratoryBirds($n, $ar) { 
    $ret = [];

    for ( $i = 0 ; $i < $n ; $i++ ){        
        $frequencia = 0;
        for ( $k = 0 ; $k < $n ; $k++) { 
            if( $ar[ $i ] == $ar[ $k ] ) {
                $ret[ $ar[ $i ] ] = 1 + $frequencia;
                $frequencia++;
            }   
        }
    }
    $arrayMaiorFrequencia = $ret[ $ar[0] ];
    $menorChaveArrayMaiorFrequencia = $ar[0];

    for ( $i = 0; $i < $n; $i++ ) {
        if( $ret[ $ar[$i] ] == $arrayMaiorFrequencia && $ar[$i] < $menorChaveArrayMaiorFrequencia ) {
            $menorChaveArrayMaiorFrequencia = $ar[$i];
        } elseif($ret[ $ar[$i] ] > $arrayMaiorFrequencia) {
            $arrayMaiorFrequencia = $ret[ $ar[$i] ];    
            $menorChaveArrayMaiorFrequencia = $ar[$i];
        }
    }

    return $menorChaveArrayMaiorFrequencia;
}

The inputs of the function are defined by the exercise, i.e., $ar is an array of int and $n is the number of elements of the array.

However, I wonder if it is possible to factor this solution? Note: despite using php, and some php functions would make the solution much easier and faster, I cannot use any PHP function, only the concept of algorithms. So how do I make my solution cleaner?

Answer 1

I start by saying that you don’t need to have 2 for to calculate frequencies:

$ret = [];

for ( $i = 0 ; $i < $n ; $i++ ){        
    $frequencia = 0;
    for ( $k = 0 ; $k < $n ; $k++) { 

Might as well do it with just one for increasing in the position that matters, working as well as a map. As to find the smallest, both your if as else if should have equal paths facilitating the algorithm. As a small aside for normal arrays, if you don’t need to use indices specifically, it becomes simpler to use foreach, because it avoids having to index constantly.

Taking into account these points I mentioned, and assuming the nomenclature of variables in Portuguese, to match what has, could do so:

function migratoryBirds($n, $ar) { 
    $passaros = [];
    foreach ($ar as $passaro){
        $passaros[$passaro] = ($passaros[$passaro] ?? 0) + 1;
    }

    $maiorContagem = 0;
    $menorId = $ar[0];
    foreach ($passaros as $id => $contagem) {
        if ($contagem > $maiorContagem || ($contagem == $maiorContagem && $id < $menorId)){
            $maiorContagem = $contagem;
            $menorId = $id;
        }
    }

    return $menorId;
}

See code working on Ideone

Notice that in this my solution I joined both cases of greater count check or equal count and smaller id:

if ($contagem > $maiorContagem || ($contagem == $maiorContagem && $id < $menorId)){

Making this part simpler.

I did the initial frequency count with just one for and I used the null coalescing Operator to fetch the value that the count for that bird already had or zero if it did not exist:

($passaros[$passaro] ?? 0)

Of course I could do this in other ways, for example at the expense of isset, if you wanted to support older versions of php.

Edit:

Surely it can only be solved with for and not foreach, I just opted for the foreach because it is simpler and idiomatic. Changing my solution to make use of only for to find the frequencies would look like this:

$passaros = [];
for ($i = 0; $i < $n; $i++){
    $passaros[$ar[$i]] = ($passaros[$ar[$i]] ?? 0) + 1;
}

According to my solution it is not possible to use a for simple in checking the largest, which is the next loop/cycle, as only a few positions are defined.

In your example of [5,5,5,3,3,3] the count array looks like this:

array(2) {
  [5]=>
  int(3)
  [3]=>
  int(3)
}

Here you see that only the position 3 and 5 are assigned, which means I can’t go through the 0.1.2 positions, etc... to the size that would be 2.

---

You can also do this first for without null coalescing Operator and using isset:

$passaros = [];
for ($i = 0; $i < $n; $i++){
    //se a contagem para este pássaro ainda não existe define como 0
    if(!isset($passaros[$a[$i]]){
        $passaros[$ar[$i]] = 0;
    }

    $passaros[$ar[$i]]++;
}

Answer 2

@Isac,

I was able to reach the following solution using 1 for and 1 if only

function migratoryBirds($n, $ar) { 
    $contagem = 0;
    $passaro = [];
    $maior = 0;
    $menorChave= 0 ;
    for($i=0; $i < $n; $i++ ){
        $passaro[$ar[$i]] = ( $passaro[ $ar[$i] ] ?? 0 ) + 1;
        if($passaro[$ar[$i]] > $maior || $passaro[$ar[$i]] == $maior && $ar[$i] < $menorChave ) {
            $maior = $passaro[$ar[$i]];
            $menorChave = $ar[$i];  
        }
    }   
    return $menorChave;
}