laurent_r

These are some answers to the Week 269, Task 1, of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few days from now (on May 19, 2024 at 23:59). This blog post provides some solutions to this challenge. Please don’t read on if you intend to complete the challenge on your own.

Task 1: Bitwise OR

You are given an array of positive integers, @ints.

Write a script to find out if it is possible to select two or more elements of the given array such that the bitwise OR of the selected elements has at least one trailing zero in its binary representation.

Example 1

Input: @ints = (1, 2, 3, 4, 5)
Output: true

Say, we pick 2 and 4, their bitwise OR is 6. The binary representation of 6 is 110.
Return true since we have one trailing zero.

Example 2

Input: @ints = (2, 3, 8, 16)
Output: true

Say, we pick 2 and 8, their bitwise OR is 10. The binary representation of 10 is 1010.
Return true since we have one trailing zero.

Example 3

Input: @ints = (1, 2, 5, 7, 9)
Output: false

First, we should state that the binary representation of an integer has a trailing zero if (and only if) it is an even number. Second, we should notice that a bitwise OR between two integers will yield an even number only if both numbers are even: if any of the two integers is odd (binary representation with a trailing 1), then the bitwise OR between them will also have a trailing 1 (and it will be odd).

To illustrate this, the following small Raku program performs a bitwise OR between all combinations of integers between 0 and 8:

say "\t", join " ", 0..8;
for 0..8 -> $i {
    say "$i\t", join " ", map { $i +| $_}, 0..8;
}

This program displays the following output:

        0 1 2 3 4 5 6 7 8
0       0 1 2 3 4 5 6 7 8
1       1 1 3 3 5 5 7 7 9
2       2 3 2 3 6 7 6 7 10
3       3 3 3 3 7 7 7 7 11
4       4 5 6 7 4 5 6 7 12
5       5 5 7 7 5 5 7 7 13
6       6 7 6 7 6 7 6 7 14
7       7 7 7 7 7 7 7 7 15
8       8 9 10 11 12 13 14 15 8

In other words, it will be "possible to select two or more elements of the given array such that the bitwise OR of the selected elements has least one trailing zero in its binary representation" if and only if there are at least two even integers in the input list. So, all we need to do is to count the number of even integers in the input list.

Bitwise OR in Raku

Based on the explanations above, we simply count the number of even numbers and return True if this count is two or more (and False otherwise).

sub bitwise-or (@in) {
    my @evens = grep { $_ %% 2 }, @in;
    return @evens.elems >= 2 ?? True !! False;
}

my @tests = (1, 2, 3, 4, 5), (2, 3, 8, 16), (1, 2, 5, 7, 9);
for @tests -> @test {
    printf "%-12s => ", "@test[]";
    say bitwise-or @test;
}

This program displays the following output:

$ raku ./bitwise-or.raku
1 2 3 4 5    => True
2 3 8 16     => True
1 2 5 7 9    => False

Bitwise OR in Perl

Based on the explanations above, we simply count the number of even numbers and return "True" if this count is two or more (and "False" otherwise).

use strict;
use warnings;
use feature 'say';

sub bitwise_or {
    my @evens = grep { $_ % 2 == 0} @_;
    return scalar @evens >= 2 ? "True" : "False";
}

my @tests = ([1, 2, 3, 4, 5], [2, 3, 8, 16], [1, 2, 5, 7, 9]);
for my $test (@tests) {
    printf "%-12s => ", "@$test";
    say bitwise_or @$test;
}

This program displays the following output:

$ perl  ./bitwise-or.pl
1 2 3 4 5    => True
2 3 8 16     => True
1 2 5 7 9    => False

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on May 26, 2024. And, please, also spread the word about the Perl Weekly Challenge if you can.