The Weekly Challenge 268

Magic Number • Number Game

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:

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

Task 2: Number Game

Prompt: You are given an array of integers, @ints, with even number of elements.

Write a script to create a new array made up of elements of the given array. Pick the two smallest integers and add it to new array in decreasing order i.e. high to low. Keep doing until the given array is empty.

Method Explanation

A direct simulation that repeatedly searches for and deletes the two minimum elements from the collection requires $O(n^2)$ operations.

Notice that once the original list is sorted in non-decreasing order:

sorted[0] ≤ sorted[1] ≤ sorted[2] ≤ sorted[3] ≤ ... ≤ sorted[2k] ≤ sorted[2k+1]

The two smallest elements in any remaining step are always the next adjacent pair $(sorted[2i], sorted[2i+1])$. To append them in decreasing order (high to low), we simply append $sorted[2i+1]$ followed by $sorted[2i]$.

This simplification runs in $O(n \log n)$ time due to sorting and requires $O(n)$ space for the transformed output.

Perl Solution

sub number_game ($ints) {
    if ( scalar @$ints % 2 != 0 ) {
        die "Input array must contain an even number of elements\n";
    }

    my @sorted = sort { $a <=> $b } @$ints;
    my @result;

    for ( my $i = 0 ; $i < @sorted ; $i += 2 ) {
        push @result, ( $sorted[ $i + 1 ], $sorted[$i] );
    }

    return \@result;
}

Python Solution

def number_game(ints: list[int]) -> list[int]:
    """Play the number game by picking pairs of smallest integers."""
    if len(ints) % 2 != 0:
        raise ValueError("Input list must contain an even number of elements")

    sorted_ints = sorted(ints)
    result: list[int] = []

    for i in range(0, len(sorted_ints), 2):
        result.extend([sorted_ints[i + 1], sorted_ints[i]])

    return result