Task 1: Magic Number
Prompt: You are given two arrays of integers of same size, @x and @y.
Write a script to find the magic number that when added to each element of one of the array gives the second array. Elements order is not important.
Method Explanation
If adding a constant integer $m$ to each element of array $x$ transforms its multiset of values into array $y$, then order is preserved because scalar addition is strictly monotonic ($a \le b \iff a + m \le b + m$).
Consequently, when both arrays are sorted in ascending order:
- The smallest element of $x$ must map directly to the smallest element of $y$: $m = y[0] - x[0]$.
- Every subsequent element must satisfy $y[i] - x[i] = m$ for all $0 \le i < n$.
If all differences match $m$, then $m$ is our unique magic number. If any difference deviates, no valid magic number exists. This eliminates the need for an $O(n^2)$ candidate search, running in optimal $O(n \log n)$ time driven by sorting.
Perl Solution
sub find_magic_number ( $x, $y ) {
die "Arrays must not be empty\n" if !@$x || !@$y;
die "Arrays must be of the same size\n" if @$x != @$y;
my @sorted_x = sort { $a <=> $b } @$x;
my @sorted_y = sort { $a <=> $b } @$y;
my $diff = $sorted_y[0] - $sorted_x[0];
for my $i ( 0 .. $#sorted_x ) {
if ( $sorted_y[$i] - $sorted_x[$i] != $diff ) {
die "No magic number found\n";
}
}
return $diff;
}
Python Solution
def find_magic_number(x: list[int], y: list[int]) -> int:
"""Find the magic number that transforms array x into array y when added."""
if len(x) != len(y):
raise ValueError("Input arrays must be of the same size")
if not x or not y:
raise ValueError("Input arrays must not be empty")
sorted_x = sorted(x)
sorted_y = sorted(y)
diff = sorted_y[0] - sorted_x[0]
for xi, yi in zip(sorted_x, sorted_y):
if yi - xi != diff:
raise ValueError("No magic number found")
return diff