PWC 367 Overlapping Oddities

Source: Dev.to

Task 1 – Maximum Odd Binary

It’s the week of the Artemis 2 mission to the moon, and we have a problem about odd numbers. I’d call that a Space Oddity.

You are given a binary string that has at least one 1. Write a script to rearrange the bits so that the resulting binary number is the maximum odd binary number and return the resulting binary string. The resulting string may contain leading zeros.

Cogitation

• To be as large as possible, a binary number must have all its 1s in the most‑significant bits.
• To be odd, the least‑significant bit must be a 1.

So we need to shift all the 1s to the left, keep one 1 at the right‑most position, and let the 0s fill the space between them.

Three possible solutions

1. Sort

sub mobSort ($str) {
    my @bits = sort { $b cmp $a } split //, $str;   # descending → 1s left
    push @bits, shift @bits;                       # rotate leftmost 1 to the end
    return join "", @bits;
}

Sort in descending order to put 1s on the left. Rotate by taking the leftmost bit and pushing it onto the right.

2. Split

sub mobSplit ($str) {
    my @bit = ("", "");                # index 0 → zeros, 1 → ones
    $bit[$_] .= $_ for split //, $str; # accumulate each character

    substr($bit[1], -1, 0, $bit[0]);   # insert the zeros just before the final 1
    return $bit[1];
}

We keep two strings, one for 0s and one for 1s. substr with a length of 0 inserts the zeros right before the last 1.

3. Count

sub mobCount ($str) {
    my $n    = length $str;
    my $zero = ($str =~ tr/0//);          # count zeros

    # (n‑zero‑1) ones on the left, then all zeros, then the final 1
    return ("1" x ($n - $zero - 1)) . ("0" x $zero) . "1";
}

tr/// returns the number of characters replaced, which we use to count zeros. The output length matches the input length.

Performance (simple benchmark)

               Rate   sorting   splitting   counting
sorting    128 205/s        --        -28%       -95%
splitting  178 571/s       39%         --       -93%
counting  2 500 000/s    1850%      1300%         --

Sorting is O(n log n) and therefore the slowest. Counting is dramatically faster.

Task 2 – Conflict Events

You are given two events, each defined by a start and an end time. Write a script to determine whether the two events conflict (i.e., have a non‑empty intersection).

Definition of conflict

• A conflict occurs when the intervals overlap for at least one minute.
• If one event ends exactly when the other starts, no conflict (the intersection is empty).

Example cases

Approach

1. Convert each HH:MM string to the number of minutes since midnight.
2. Normalize ranges that cross midnight using modulo arithmetic.
3. Check whether two ranges overlap.

Helper functions (Perl)

# Convert "HH:MM" → minutes since midnight
sub toMinute ($hhmm) {
    my ($h, $m) = split ":", $hhmm;
    return $m + 60 * $h;
}

# Turn a pair of minute values into a normalized range [beg, end)
# Handles intervals that span midnight.
sub toRange ($minBeg, $minEnd) {
    my $duration = ($minEnd - $minBeg) % 1440;   # length of the event
    return [ $minEnd - $duration, $minEnd ];    # may be negative → before midnight
}

# Determine whether two half‑open ranges overlap.
sub isOverlap ($range1, $range2) {
    use enum qw( BEG=0 END=1 );                  # for readability
    return $range1->[END] > $range2->[BEG] &&   # end of 1 after start of 2
           $range1->[BEG] < $range2->[END];     # start of 1 before end of 2
}

# Main API: given two arrayrefs ["HH:MM","HH:MM"], return true/false
sub isConflict ($event1, $event2) {
    return isOverlap(
        toRange( map { toMinute($_) } $event1->@* ),
        toRange( map { toMinute($_) } $event2->@* )
    );
}

• toMinute parses the hour and minute components.
• toRange computes the actual start (beg) and end (end) values, correctly handling midnight wrap‑around.
• isOverlap checks the classic interval‑overlap condition for half‑open intervals [beg, end).
• isConflict ties everything together, accepting two array references representing the events.

Usage example

my $e1 = [ "23:30", "00:30" ];
my $e2 = [ "00:00", "01:00" ];

say isConflict($e1, $e2) ? "true" : "false";   # prints "true"

The script now correctly identifies conflicts, including those that span midnight.