The Weekly Challenge 301

Largest Number & Hamming Distance

Solutions on GitHub

Task 1: Largest Number

You are given a list of positive integers. Write a script to arrange them such that they form the largest possible number.

Example Output

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

Logic

A standard numerical descending sort is not sufficient because comparing numbers like 3 and 30 lexicographically or numerically would order 30 before 3, giving 303 instead of the optimal 330. Instead, we define a custom comparator for any two numbers a and b by comparing the string concatenations: compare b . a with a . b. If b . a > a . b, b should precede a.

Perl Solution

ch-1.pl

sub largest_number ($ints) { ($ints) = $LIST_CHECK->($ints); die 'Expected positive integers' if grep { $_ <= 0 } @$ints; my @sorted = sort { ( "$b$a" cmp "$a$b" ) || ( $b <=> $a ) } @$ints; return join '', @sorted; }

Python Solution

ch-1.py

def _compare(a: str, b: str) -> int: ab = a + b ba = b + a if ab > ba: return -1 if ab < ba: return 1 return 0 def largest_number(ints: Sequence[int]) -> str: if any(value <= 0 for value in ints): raise ValueError("Expected positive integers") parts = [str(value) for value in ints] parts.sort(key=cmp_to_key(_compare)) return "".join(parts)

Task 2: Hamming Distance

You are given an array of integers. Write a script to calculate the sum of Hamming distances for all pairs of the given integers.

Example Output

Input: @ints = (4, 14, 2) Output: 6 Explanation: 4 = 0100 14 = 1110 2 = 0010 HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. Input: @ints = (4, 14, 4) Output: 4

Logic

The Hamming distance between two numbers is the number of bit positions in which the corresponding bits are different. In binary arithmetic, this corresponds to the bitwise XOR (a ^ b) followed by counting the set bits (population count / popcount). We compute this across all unordered pairs (i, j) with i < j.

Perl Solution

ch-2.pl

sub _popcount ($n) { my $count = 0; while ($n) { $n &= ( $n - 1 ); ++$count; } return $count; } sub hamming_distance_sum ($ints) { ($ints) = $LIST_CHECK->($ints); return 0 if @$ints < 2; my $sum = 0; for my $i ( 0 .. $#$ints - 1 ) { for my $j ( $i + 1 .. $#$ints ) { $sum += _popcount( $ints->[$i] ^ $ints->[$j] ); } } return $sum; }

Python Solution

ch-2.py

def hamming_distance_sum(ints: Sequence[int]) -> int: total = 0 for i in range(len(ints) - 1): for j in range(i + 1, len(ints)): total += bin(ints[i] ^ ints[j]).count("1") return total