The Weekly Challenge #397

Task 1: Absent Smallest Positive

Method Explanation

The problem requires identifying an integer $k$ that satisfies three properties:

1. $k \ge 1$ (it must be a positive integer).
2. $k > \text{average}$ (strictly greater than the arithmetic mean of the input array).
3. $k \notin \text{array}$ (it is absent from the input array).

We first compute the average: $$\text{avg} = \frac{\sum_{x \in \text{arr}} x}{|\text{arr}|}$$ The initial candidate is the smallest positive integer strictly exceeding $\text{avg}$: $$k = \max(1, \lfloor \text{avg} \rfloor + 1)$$ If $k \le \text{avg}$ (which can happen when $\text{avg}$ is an exact integer), we increment $k$ to $k + 1$.

Finally, we store the elements of the array in a hash set for $O(1)$ lookup time and increment $k$ while $k$ is present in the set. Because we examine sequential integers starting from the lowest valid candidate, the first absent value found is guaranteed to be minimal.

Perl Implementation

sub absent_smallest_positive ($arr) {
    ($arr) = $INTS_CHECK->($arr);
    die 'Array cannot be empty' if !@$arr;

    my $sum = 0;
    $sum += $_ for @$arr;
    my $avg = $sum / scalar(@$arr);

    my %lookup = map { $_ => 1 } @$arr;

    my $candidate = floor($avg) + 1;
    $candidate = 1 if $candidate < 1;

    if ( $candidate <= $avg ) {
        $candidate++;
    }

    while ( exists $lookup{$candidate} ) {
        $candidate++;
    }

    return $candidate;
}

Python Implementation

def absent_smallest_positive(arr: Sequence[int]) -> int:
    """Return smallest absent positive integer strictly greater than average of elements."""
    if not arr:
        raise ValueError("Array cannot be empty")

    avg = sum(arr) / len(arr)
    lookup = set(arr)

    candidate = max(1, math.floor(avg) + 1)
    if candidate <= avg:
        candidate += 1

    while candidate in lookup:
        candidate += 1

    return candidate

Task 2: Binary Reflection

Method Explanation

The binary reflection of an integer $N$ is computed by:

1. Converting $N$ to its standard binary string representation without leading zeros (e.g., $10_{10} \to 1010_2$, $6_{10} \to 110_2$).
2. Reversing the binary string (e.g., $1010_2 \to 0101_2$, $110_2 \to 011_2$).
3. Interpreting the reversed binary string as a decimal value (e.g., $0101_2 \to 5_{10}$, $011_2 \to 3_{10}$).

We sort the array using a composite key: $$(\text{binary\_reflection}(x), x)$$ This naturally sorts by reflected value first and uses the original integer value as an ascending tie-breaker.

Perl Implementation

sub binary_reflection ($num) {
    return 0 if $num == 0;
    my $bin = sprintf( '%b', $num );
    my $rev = reverse $bin;
    return oct( "0b$rev" );
}

sub sort_by_binary_reflection ($arr) {
    ($arr) = $INTS_CHECK->($arr);
    return [] if !@$arr;

    my @decorated = map { [ $_, binary_reflection($_) ] } @$arr;

    @decorated = sort {
        $a->[1] <=> $b->[1] || $a->[0] <=> $b->[0]
    } @decorated;

    return [ map { $_->[0] } @decorated ];
}

Python Implementation

def binary_reflection(num: int) -> int:
    """Return decimal value of the reversed binary representation of num."""
    if num == 0:
        return 0
    bin_str = bin(num)[2:]
    return int(bin_str[::-1], 2)


def sort_by_binary_reflection(arr: Sequence[int]) -> list[int]:
    """Sort arr ascending by binary reflection, breaking ties by original value."""
    return sorted(arr, key=lambda x: (binary_reflection(x), x))