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