03 January 2025

Challenge 301

Distant Sorting

• Task 1: Largest Number
• Task 2: Hamming Distance

Task 1: Largest Number

Submitted by: Mohammad Sajid Anwar

---

You are given a list of positive integers, @ints.

Write a script to arrange all the elements in the given list such that they form the largest number and return it.

Example 1

Input: @ints = (20, 3)
Output: 320

Example 2

Input: @ints = (3, 30, 34, 5, 9)
Output: 9534330

---

Solution

All we need for this task is a specially crafted comparison function between $a and $b:

• if the first digits of $a and $b differ, the number with the larger leader goes first
• if $a and $b have the same leading digit and have both a length of 1, they are equal
• otherwise, i.e. $a and $b have the same leading digit and at least one of them has a length greater then 1, we strip the leading digit from any number having more than one digit and perform a recursive comparison with the modified values.

This would be a case for goto &sub, but perl does not permit this statement in a sort sub.

use strict;
use warnings;

sub numcat {
    my $cmp = substr($b, 0, 1) <=> substr($a, 0, 1);
    return $cmp if $cmp;
    return 0 if length($a) == 1 && length($b) == 1;
    local $a = substr $a, 1 if length($a) > 1;
    local $b = substr $b, 1 if length($b) > 1;
    numcat();
}

sub largest_number {
    join '', sort numcat @_;
}

See the full solution to task 1.

Task 2: Hamming Distance

Submitted by: Mohammad Sajid Anwar

---

You are given an array of integers, @ints.

Write a script to return the sum of Hamming distances between all the pairs of the integers in the given array of integers.

The Hamming distance between two integers is the number of places in which their binary representations differ.

Example 1

Input: @ints = (4, 14, 2)
Output: 6

Binary representation:
4  => 0100
14 => 1110
2  => 0010

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2

Input: @ints = (4, 14, 4)
Output: 4

---

Solution

There is no need to calculate the Hamming distance between all pairs of the given numbers. Actually, there is no need to calculate any Hamming distance at all.

Given the numbers \((p_0,\ldots,p_{n-1})\), we build a binary matrix \(B = (b_{ik})\) from the numbers’ binary representation such that:

\[p_i = \sum_{k = 0}^{l - 1} b_{ik} 2^k\]

Now we take the sum over the individual bit positions as

\[c_k = \sum_{i = 0}^{n - 1} b_{ik}\]

At the bit position \(k\), we find \(c_k\) ones and \(n - c_k\) zeros. Each zero paired with a one accounts for \(1\) in the sum of the Hamming distances and there are \(c_k (n - c_k)\) such pairs.

Therefore we find the sum over the pairwise Hamming distances of the given numbers as:

\[H = \sum_{k=0}^{l-1} c_k (n - c_k)\]

Note 1: The Hamming distance between positive and negative numbers doesn’t make much sense. Relying on Math::Prime::Util::todigits’s behavior, which returns the digits of \(|n|\).

Note 2: When providing a list of two numbers, this procedure will calculate their Hamming distance, though in a rather strange way.

use strict;
use warnings;
use PDL;
use Math::Prime::Util 'todigits';

sub hamming_distance_sum {
    my $b = long [map [reverse todigits $_, 2], @_];
    my $c = $b->xchg(0, 1)->sumover;

    sum $c * ($b->dim(1) - $c);
}

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.