The Weekly Challenge 269

Bitwise OR with Trailing Zero • Distribute Elements

Task 1: Bitwise OR

Prompt: You are given an array of 2-or-more positive integers, @ints. Write a script to find out if it is possible to select two or more elements of @ints such that the bitwise OR of those elements has at least one trailing zero in its binary representation.

Method Explanation

An integer in binary representation ends with at least one trailing zero if and only if it is divisible by 2 (i.e. it is an even integer with least significant bit $b_0 = 0$).

The bitwise OR operator (|) produces $0$ at the lowest bit position if and only if both bits are $0$:

For any selection of $k \ge 2$ integers, their bitwise OR has a trailing zero if and only if every selected integer is even. If any selected integer is odd, the least significant bit immediately becomes 1, eliminating any trailing zero.

Therefore, a suitable subset of two or more elements exists if and only if the array contains at least two even numbers.

Instead of testing all pairs in $O(n^2)$ time, we can simply scan the array in $O(n)$ time and count the even numbers, returning true as soon as we encounter the second even integer.

Perl Solution

sub bitwise_or_with_trailing_zero ($ints) {
    my $even_count = 0;
    for my $val (@$ints) {
        if ( $val % 2 == 0 ) {
            $even_count++;
            return 1 if $even_count >= 2;
        }
    }
    return 0;
}

Python Solution

def bitwise_or_with_trailing_zero(ints: list[int]) -> bool:
    """Determine if two or more elements can be selected with a bitwise OR having a trailing zero."""
    even_count = 0
    for num in ints:
        if num % 2 == 0:
            even_count += 1
            if even_count >= 2:
                return True
    return False

Task 2: Distribute Elements

Prompt: You are given an array, @ints, of 2-or-more distinct integers. Write a script to distribute the elements as described below:

  1. Move the 1st element of @ints to a new array @arr1.
  2. Move the 2nd element of @ints to a new array @arr2.
  3. Repeatedly move the next element of @ints to @arr1 or @arr2, depending on these criteria:
    • If the last element of @arr1 is greater than the last element of @arr2, move the element to the end of @arr1.
    • Otherwise, move the element to the end of @arr2.
  4. Once @ints is empty, return the concatenated arrays (@arr1, @arr2).

Method Explanation

This task specifies an explicit sequential simulation:

By indexing or slicing rather than repeatedly calling shift or pop(0) on large collections, the simulation runs cleanly in $O(n)$ time and requires $O(n)$ additional storage.

Perl Solution

sub distribute_elements ($ints) {
    my @remaining = @$ints;
    return []           if @remaining == 0;
    return [@remaining] if @remaining == 1;

    my @arr1 = ( shift @remaining );
    my @arr2 = ( shift @remaining );

    for my $elem (@remaining) {
        if ( $arr1[-1] > $arr2[-1] ) {
            push @arr1, $elem;
        }
        else {
            push @arr2, $elem;
        }
    }

    return [ @arr1, @arr2 ];
}

Python Solution

def distribute_elements(ints: list[int]) -> list[int]:
    """Distribute elements into two lists according to last element comparisons."""
    if len(ints) <= 1:
        return list(ints)

    arr1: list[int] = [ints[0]]
    arr2: list[int] = [ints[1]]

    for elem in ints[2:]:
        if arr1[-1] > arr2[-1]:
            arr1.append(elem)
        else:
            arr2.append(elem)

    return arr1 + arr2