The Weekly Challenge 262

Max Positive Negative & Count Equal Divisible: Sign Partition Counting and Divisible Index Pair Enumeration in Perl & Python

Lubos Kolouch March 24, 2024 Challenge Details GitHub Solutions

Task 1: Max Positive Negative

You are given an array of integers, @ints.

Write a script to return the maximum number of either positive or negative integers in the given array.

Example 1: Input: @ints = (-3, 1, 2, -1, 3, -2, 4) → Output: 4 (4 positive, 3 negative)

Example 2: Input: @ints = (-1, -2, -3, 1) → Output: 3

Example 3: Input: @ints = (1, 2) → Output: 2

Method Explanation

To determine the larger count between strictly positive (> 0) and strictly negative (< 0) elements in @ints (remembering that 0 is neither positive nor negative):

  1. Count the number of elements strictly greater than zero.
  2. Count the number of elements strictly less than zero.
  3. Return the maximum of the two counts.

Scanning the array takes $O(N)$ time and $O(1)$ auxiliary space.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for max_positive_negative => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub max_positive_negative ($ints) {
    my $positive_count = scalar( grep { $_ > 0 } @$ints );
    my $negative_count = scalar( grep { $_ < 0 } @$ints );
    return $positive_count > $negative_count ? $positive_count : $negative_count;
}

Python Solution

def max_positive_negative(ints: list[int]) -> int:
    """Return the maximum count of either positive or negative integers."""
    positive_count = sum(1 for x in ints if x > 0)
    negative_count = sum(1 for x in ints if x < 0)
    return max(positive_count, negative_count)

Task 2: Count Equal Divisible

You are given an array of integers, @ints, and an integer $k.

Write a script to return the number of pairs (i, j) where:

  • 0 ≤ i < j < size of @ints
  • ints[i] == ints[j]
  • i × j is divisible by k

Example 1: Input: @ints = (3, 1, 2, 2, 2, 1, 3), $k = 2 → Output: 4

Example 2: Input: @ints = (1, 2, 3), $k = 1 → Output: 0

Method Explanation

We need to count all 0-based index pairs (i, j) with i < j where the array values match and the product of indices is a multiple of $k:

  1. Iterate i from 0 to N - 1 and j from i + 1 to N - 1.
  2. Check whether ints[i] == ints[j] and (i * j) % k == 0, incrementing our counter whenever both conditions hold.

This nested loop runs in $O(N^2)$ time and $O(1)$ space.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for count_equal_divisible => (
    method     => 0,
    positional => [ ArrayRef [Int], Int ],
);

sub count_equal_divisible ( $ints, $k ) {
    my $count = 0;
    my $n     = scalar @$ints;

    for my $i ( 0 .. $n - 1 ) {
        for my $j ( $i + 1 .. $n - 1 ) {
            if ( $ints->[$i] == $ints->[$j] && ( $i * $j ) % $k == 0 ) {
                $count++;
            }
        }
    }
    return $count;
}

Python Solution

def count_equal_divisible(ints: list[int], k: int) -> int:
    """Count pairs (i, j) with 0 <= i < j < len(ints), ints[i] == ints[j], and (i * j) % k == 0."""
    count = 0
    n = len(ints)
    for i in range(n):
        for j in range(i + 1, n):
            if ints[i] == ints[j] and (i * j) % k == 0:
                count += 1
    return count