12 July 2024

Challenge 277

Common Strength

• Task 1: Count Common
• Task 2: Strong Pair

Task 1: Count Common

Submitted by: Mohammad Sajid Anwar

---

You are given two array of strings, @words1 and @words2.

Write a script to return the count of words that appears in both arrays exactly once.

Example 1

Input: @words1 = ("Perl", "is", "my", "friend")
       @words2 = ("Perl", "and", "Raku", "are", "friend")
Output: 2

The words "Perl" and "friend" appear once in each array.

Example 2

Input: @words1 = ("Perl", "and", "Python", "are", "very", "similar")
       @words2 = ("Python", "is", "top", "in", "guest", "languages")
Output: 1

Example 3

Input: @words1 = ("Perl", "is", "imperative", "Lisp", "is", "functional")
       @words2 = ("Crystal", "is", "similar", "to", "Ruby")
Output: 0

---

Solution

With almost no extra effort the task may be generalized to an arbitrary number of arrays. To identify the single common words, we count all words per array and select those having a counter of one for every array.

use v5.24;
use warnings;

sub count_common {
    my %words;
    my $li = $#_;
    for my $i (0 .. $li) {
        $words{$_}[$i]++ for $_[$i]->@*;
    }
    no warnings 'uninitialized';

    grep {$li + 1 == grep $_ == 1, $words{$_}->@[0..$li]} keys %words
}

See the full solution to task 1.

Task 2: Strong Pair

Submitted by: Mohammad Sajid Anwar

---

You are given an array of integers, @ints.

Write a script to return the count of all strong pairs in the given array.

A pair of integers x and y is called strong pair if it satisfies:

\(0 < |x - y| < \min(x, y)\).

Example 1

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

Strong Pairs: (2, 3), (3, 4), (3, 5), (4, 5)

Example 2

Input: @ints = (5, 7, 1, 7)
Ouput: 1

Strong Pairs: (5, 7)

---

Solution

Without loss of generality we may assume \(y \ge x\). Then we find:

\[\begin{alignat*}{2} 0 &< |x - y| &< & \; \min(x, y) \\ 0 &< y - x &< & \; x \\ x &< y &< & \; 2 x \end{alignat*}\]

Furthermore, from example 2 we may conclude that only unique pair values shall be counted. For this purpose we consider unique values from \(I = (i_1,\ldots,i_n)\) and sort these in ascending order. Let \(S = (s_1,\ldots,s_k)\) be the sorted, unique values from \(I\). Then for all \(i < j\) the inequality \(s_i < s_j\) is satisfied.

Considering the second inequality \(y < 2 x\):
We define a function

\[xd(i) = \min(\{j \in \Bbb{N} \, | \, i < j \le k \wedge s_j \ge 2 s_i\} \cup \{k + 1\})\]

that provides the smallest index \(j\) where \(s_j\) hits or exceeds the double of \(s_i\) – if such an index exists – and one beyond the last index of \(S\) otherwise.

For a fixed \(i\), all pairs \((s_i, s_j)\) having \(i < j < xd(i)\) form strong pairs and their count is \(xd(i) - i - 1\).

An important detail about \(xd(i)\) is the time complexity to calculate the values for all \(i\): This can be done in a single pass over \(S\) using two monotonous indices in \(\mathcal{O}(k)\). The time complexity of the whole algorithm is then dominated by the sort as \(\mathcal{O}(n \log n)\).

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

sub strong_pairs {
    my @ints = uniqint sort {$a <=> $b} @_;
    my ($yi, $cnt) = (1, 0);
    for my $xi (0 .. $#ints) {
        my $x = $ints[$xi];
        $yi++ while $yi < @ints && $ints[$yi] < 2 * $x;
        $cnt += $yi - $xi - 1;
    }

    $cnt;
}

See the full solution to task 2.

See discussion.

---

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.