Smaller than Current & Reduced Row Echelon
You are given an array of integers, @ints. Write a script to find out how many integers are smaller than current, i.e., for each ints[i], count ints[j] < ints[i] where i != j.
For each element y in the input array, count how many elements x in the same array satisfy x < y. Because strict inequality (<) never matches the element against itself, checking i != j is unnecessary. Time complexity is O(n²) and space complexity is O(n) for the output array.
ch-1.pl)#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
use Test::More;
signature_for smaller_than_current => (
method => 0,
positional => [ ArrayRef [Int] ],
);
sub smaller_than_current ($ints) {
return [
map {
my $x = $_;
scalar grep { $_ < $x } @$ints
} @$ints
];
}
ch-1.py)def smaller_than_current(ints: list[int] | tuple[int, ...]) -> list[int]:
"""Return for each element the count of elements strictly smaller than it."""
return [sum(x < y for x in ints) for y in ints]
Given a matrix M, check whether the matrix is in reduced row echelon form (RREF). A matrix is in RREF if:
1 (the leading 1).We iterate through the matrix row by row while tracking last_leading (initially -1) and a zero_row_encountered flag. If a row is all zeros, we set the flag and continue. If we see a non-zero row after a zero row, we return 0. Otherwise, we locate the first non-zero entry: if it is not 1 or its column index is not strictly greater than last_leading, we return 0. Finally, we verify that all other rows have 0 in that leading column. If all rows pass, we return 1.
ch-2.pl)#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);
use Test::More;
signature_for is_reduced_row_echelon => (
method => 0,
positional => [ ArrayRef [ ArrayRef [Int] ] ],
);
sub is_reduced_row_echelon ($matrix) {
my $last_leading = -1;
my $zero_row_encountered = 0;
for my $row_index ( 0 .. $#{$matrix} ) {
my $row = $matrix->[$row_index];
my $leading = -1;
for my $i ( 0 .. $#{$row} ) {
my $element = $row->[$i];
if ( $element != 0 ) {
return 0 if $element != 1;
$leading = $i;
last;
}
}
if ( $leading == -1 ) {
$zero_row_encountered = 1;
next;
}
return 0 if $zero_row_encountered;
return 0 if $leading <= $last_leading;
for my $r_index ( 0 .. $#{$matrix} ) {
next if $r_index == $row_index;
return 0 if $matrix->[$r_index][$leading] != 0;
}
$last_leading = $leading;
}
return 1;
}
ch-2.py)def is_reduced_row_echelon(matrix: list[list[int]]) -> int:
"""Return 1 if matrix is in reduced row echelon form, otherwise 0."""
last_leading = -1
zero_row_encountered = False
for row_idx, row in enumerate(matrix):
if all(x == 0 for x in row):
zero_row_encountered = True
continue
if zero_row_encountered:
return 0
leading = next(i for i, x in enumerate(row) if x != 0)
if row[leading] != 1 or leading <= last_leading:
return 0
if any(
matrix[i][leading] != 0
for i in range(len(matrix))
if i != row_idx
):
return 0
last_leading = leading
return 1