THE WEEKLY CHALLENGE - 241

https://theweeklychallenge.org/blog/perl-weekly-challenge-241/

Table of Contents

• Task1-Arithmetic Triplets
• Task2-Prime Order

Task 1 - Arithmetic Triplets

Problem Statement

You are given an array of integers sorted in ascending order and a positive integer called diff. Your task is to find the number of unique arithmetic triplets in the array that satisfy the following conditions:

1. ( i < j < k )
2. nums[j] - nums[i] = diff
3. nums[k] - nums[j] = diff

Algorithm

To solve this problem efficiently, we can use a Set data structure to store all the numbers in the array. Then, we can iterate through the array and check whether each number ( x ) forms an arithmetic triplet ( (x - diff, x, x + diff) ) using the Set.

The algorithm can be broken down into the following steps:

1. Create an empty Set and populate it with all numbers in the array.
2. Initialize a counter variable to 0.
3. Loop through the array:
   • For each number ( x ), check if ( (x - diff) ) and ( (x + diff) ) exist in the Set.
   • If they do, increment the counter by 1.

Complexity Analysis

The algorithm has a time complexity of ( O(n) ), where ( n ) is the size of the array. This is because we only loop through the array once, and all Set operations take ( O(1) ) time.

Python Implementation

def count_arithmetic_triplets(nums, diff):
    count = 0
    nums_set = set(nums)

    for num in nums:
        if (num + diff) in nums_set and (num - diff) in nums_set:
            count += 1

    return count

# Test Cases
print(count_arithmetic_triplets([0, 1, 4, 6, 7, 10], 3))  # Output: 2
print(count_arithmetic_triplets([4, 5, 6, 7, 8, 9], 2))  # Output: 2

Perl Implementation

sub count_arithmetic_triplets {
    my ($nums, $diff) = @_;
    my $count = 0;
    my %nums_set = map { $_ => 1 } @$nums;

    for my $num (@$nums) {
        if (exists $nums_set{$num + $diff} && exists $nums_set{$num - $diff}) {
            $count++;
        }
    }

    return $count;
}

# Test Cases
print count_arithmetic_triplets([0, 1, 4, 6, 7, 10], 3);  # Output: 2
print count_arithmetic_triplets([4, 5, 6, 7, 8, 9], 2);  # Output: 2

Raku Implementation

sub count-arithmetic-triplets(@nums, $diff) {
    my $count = 0;
    my %nums-set = @nums.Set;

    for @nums -> $num {
        if %nums-set{$num + $diff}:exists {
            if %nums-set{$num - $diff}:exists {
                $count++;
            }
        }
    }

    return $count;
}

# Test Cases
say count-arithmetic-triplets([0, 1, 4, 6, 7, 10], 3);  # Should print 2
say count-arithmetic-triplets([4, 5, 6, 7, 8, 9], 2);  # Should print 2

That's it! This is how we can efficiently find the number of unique arithmetic triplets in an array.

Task 2 - Prime Order

The Problem

You are given an array of unique positive integers greater than 2. Write a script to sort them in ascending order of the count of their prime factors, tie-breaking by ascending value.

Example:

Input: [11, 8, 27, 4]

Output: [11, 4, 8, 27]

Analysis

The problem can be divided into two main steps:

1. Finding the prime factors for each number in the array
2. Sorting the array based on the count of the prime factors and the value itself

Algorithm

1. Create a function to find the prime factors of a given number.
2. Sort the array of numbers, using the count of prime factors as the primary key and the number itself as the secondary key.

Python Implementation

Python allows us to use the sorted function with a custom key. We'll use this to sort the array according to our needs.

from math import isqrt

def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, isqrt(n) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

def sort_by_prime_factors(nums):
    return sorted(nums, key=lambda x: (len(prime_factors(x)), x))

# Test case
print(sort_by_prime_factors([11, 8, 27, 4]))

Perl Implementation

In Perl, the sort function can be customized by defining a custom comparison subroutine. Here's how:

use strict;
use warnings;

sub prime_factors {
    my $n = shift;
    my @factors;
    while ($n % 2 == 0) {
        push @factors, 2;
        $n /= 2;
    }
    for my $i (3 .. sqrt($n)) {
        while ($n % $i == 0) {
            push @factors, $i;
            $n /= $i;
        }
    }
    push @factors, $n if $n > 2;
    return @factors;
}

sub sort_by_prime_factors {
    my @nums = @_;
    return sort { scalar(prime_factors($a)) <=> scalar(prime_factors($b)) || $a <=> $b } @nums;
}

# Test case
print join(", ", sort_by_prime_factors(11, 8, 27, 4));

Raku Implementation

Raku provides a .sort method that can accept a block of code to determine the sorting key. This makes it very convenient to implement our custom sorting logic.

sub prime-factors(Int $n is copy) {
    my @factors;
    while $n %% 2 {
        @factors.push: 2;
        $n div= 2;
    }
    for 3, 5 ... * -> $i {
        last if $i > sqrt($n);
        while $n %% $i {
            @factors.push: $i;
            $n div= $i;
        }
    }
    @factors.push: $n if $n > 2;
    return @factors;
}

sub sort-by-prime-factors(@nums) {
    my @sorted-nums = @nums.sort: { prime-factors($_).elems, $_ };
    return @sorted-nums;
}

# Test Cases
say sort-by-prime-factors([11, 8, 27, 4]);