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$:
0 | 0 = 0(even OR even = even)0 | 1 = 1(even OR odd = odd)1 | 1 = 1(odd OR odd = odd)
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