site.base_url }}/">The Bear's Den -->

The Bear's Den

Enter at your own risk

05 July 2024

Challenge 276

Hourly Frequencies

Task 1: Complete Day
Task 2: Maximum Frequency

Task 1: Complete Day

Submitted by: Mohammad Sajid Anwar

You are given an array of integers, @hours.

Write a script to return the number of pairs that forms a complete day.

A complete day is defined as a time duration that is an exact multiple of 24 hours.

Example 1

Input: @hours = (12, 12, 30, 24, 24)
Output: 2

Pair 1: (12, 12)
Pair 2: (24, 24)

Example 2

Input: @hours = (72, 48, 24, 5)
Output: 3

Pair 1: (72, 48)
Pair 2: (72, 24)
Pair 3: (48, 24)

Example 3

Input: @hours = (12, 18, 24)
Output: 0

Solution

While the definition of a complete day seems to be clear, the number of pairs is not.

Two important observations can be made from the above examples:

Pairs must be build from different elements of the given list, thought their values may be identical.
Pairs are unordered.

The key to a consistent description is to look at index pairs instead of value pairs. Thus a more formal description of this task might be:

Given an n-tuple $H = (h_1,\ldots,h_n)$ of integers, find the number of index pairs $\{i, j\}$ where $h_i \equiv h_j \bmod{24}$

Let us consider the index set $I = \{1,\ldots,n\}$. We may say that an index pair $\{i, j\} \subset I$ forms a complete day, if their corresponding values do, i.e. $h_i \equiv h_j \bmod{24}$.

The index set $I$ can be partitioned by the equivalence relation $h_i \equiv h_j \bmod{24}$, leading to subsets $P_k \subset I, 0 \le k < 24$ with $P_k = \{i \in I | h_i \equiv k \bmod{24}\}$. For the sake of convenience we permit empty subsets $P_k$.

By construction, each pair $\{i, j\} \subset P_k$ represents a complete day, while no pair from different subsets does. The number of pairs that can be formed from a set of $c$ elements is $c (c - 1) / 2$.

If $c_k$ denotes the number of elements in $P_k$, then the total number of pairs forming a complete day is:

\[\sum_{k=0}^{23} \frac{c_k (c_k - 1)}{2}\]

The effort for calculating all values $c_k$ is $\mathcal{O}(n)$ as we just need to count the number of elements in $H$ per remainder modulo 24. As the sum is calculated in $\mathcal{O}(1)$, the resulting total complexity is $\mathcal{O}(n)$.

An implementation using PDL is straightforward. For hist we use 24 bins centered at the integers 0 .. 23.

use strict;
use warnings;
use PDL;

sub complete_days {
    my $c = hist pdl(@_) % 24, -0.5, 23.5, 1;

    sum $c * ($c - 1) / 2;
}

See the full solution to task 1.

See discussion.

Task 2: Maximum Frequency

Submitted by: Mohammad Sajid Anwar

You are given an array of positive integers, @ints.

Write a script to return the total number of elements in the given array which have the highest frequency.

Example 1

Input: @ints = (1, 2, 2, 4, 1, 5)
Ouput: 4

The maximum frequency is 2.
The elements 1 and 2 has the maximum frequency.

Example 2

Input: @ints = (1, 2, 3, 4, 5)
Ouput: 5

The maximum frequency is 1.
The elements 1, 2, 3, 4 and 5 has the maximum frequency.

Solution

This task can be solved with a complexity of $\mathcal{O}(n)$. Moreover, it can be done in a single pass over the given elements.

There is no need to restrict the array elements to positive integers, not even to numbers.

Recording the elements’ frequencies in a hash %freq and the (currently observed) maximum frequency in $maxfreq, for each element $_ of the list there are three cases:

$freq{$_} < $maxfreq: The running result in $a does not change.
$freq{$_} == $maxfreq: The running result is incremented by $maxfreq.
$freq{$_} > $maxfreq: $maxfreq is set to the frequency of $_, which gives the running result simultaneously.

We may build a list of three anonymous subroutines each of which performs one of the required actions and call the sub indexed by the result of the spaceship operator <=>. (Note that an index of -1 accesses the last element of an array or list.)

use strict;
use warnings;
use List::Util 'reduce';

sub max_freq {
    my ($maxfreq, %freq) = 0;

    reduce {
        &{ ( sub {$a + $maxfreq},
             sub {$maxfreq = $freq{$b}},
             sub {$a}
           )[++$freq{$b} <=> $maxfreq]
        }()
    } 0, @_;
}

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.