Perl Weekly Challenge 66: Divide Integers and Power Integers

These are some answers to the Week 66 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Task 1: Divide Integers

You are given two integers $M and $N.

Write a script to divide the given two integers i.e. $M / $N without using multiplication, division and mod operator and return the floor of the result of the division.

Example 1:

Input: $M = 5, $N = 2
Output: 2

Example 2:

Input: $M = -5, $N = 2
Output: -3

Example 3:

Input: $M = -5, $N = -2
Output: 2

Dividing $m by $n with integer or Euclidian division is equivalent to finding how many times you can subtract $n from $m while getting a positive result. Thus the algorithm is fairly straight forward. A slight difficulty is that either $m or $n (or both) might be negative. My way to tackle the problem is to work on absolute values of the $m and $n input values, and to change the sign of the result when needed. I wish I could have used multiplication of the two input values to find the sign of the result (this is not the core of the algorithm), as this is simpler, but since multiplication is forbidden, I had to use more complicated Boolean expressions.

Divide Integers in Raku

With the above explanations, the implementation is quite straight forward:

use v6;

sub MAIN (Int $m is copy, $n is copy where $n != 0) {
    my $neg = ($m <0 && $n >0 or $m > 0 && $n < 0) ?? True !! False;
    $_ = .abs for $m, $n;
    my $quotient = 0;
    while $m > $n {
        $m -= $n;
        $quotient++;
    }
    $quotient = -$quotient if $neg;
    say $quotient;
}

Running the script with various input values yields the following results:

$ perl6 int-division.p6 -5 2
-2

$ perl6 int-division.p6 5 -2
-2

$ perl6 int-division.p6 -5 -2
2

$ perl6 int-division.p6 5 2
2

Divide Integers in Perl

This is a port to Perl of the above Raku program:

use strict;
use warnings;
use feature qw /say/;

die "Two integers needed!" unless @ARGV == 2;
my ($m, $n) = @ARGV;
die "Second argument cannot be 0" if $n == 0;
my $neg = ($m <0 && $n >0 or $m > 0 && $n < 0) ? 1 : 0;
$_ = abs $_ for $m, $n;
my $quotient = 0;
while ($m > $n) {
    $m -= $n;
    $quotient++;
}
$quotient = -$quotient if $neg;
say $quotient;

This program displays the following output for various input data:

$ perl int-division.pl 5 2
2

$ perl int-division.pl -5 2
-2

$ perl int-division.pl -5 -2
2

$ perl int-division.pl 5 -2
-2

$ perl int-division.pl 5 0
Second argument cannot be 0 at int-division.pl line 7.

Task 2: Power Integers

You are given an integer n.

Write a script to check if the given number can be expressed as m ** n where m and n are positive integers. Otherwise print 0.

Please make sure m > 1 and n > 1.

BONUS: If there are more than one ways to express the given number then print all possible solutions.

Example 1:

For given $N = 9, it should print 32 or 3^2.

Example 2:

For given $N = 45, it should print 0.

Example 3:

For given $N = 64, it should print all or one of 8^2 or 2^6 or 4^3.

I think that there should probably a better way to do it, but since I'm late and I don't have very much time to really think about it, I'll use a brute force approach in which I first find the prime factors of the input number, then find all factors less than or equal to the square root of the input number, and finally find all the combinations whose product is equal to the input number.

Please note that I'm quite late and will only provide a Raku solution. It should be pretty easy to port the Raku program to Perl.

Power Integers in Raku

use v6;

my @primes = grep { .is-prime }, 1 .. *;

sub prime-factors (UInt $num-in is copy) {
    my @factors;
    my $num = $num-in;
    for @primes -> $div {
        while ($num %% $div) {
            push @factors, $div;
            $num div= $div;
        }
        return @factors if $num == 1;
    }
    push @factors, $num unless $num == $num-in;
    return @factors;
}

sub find-powers (Int $n) {
    my @prime-factors = prime-factors $n;
    my $max = sqrt $n;
    return 0 unless @prime-factors;
    my @factors = @prime-factors.combinations.map({[*] $_}).grep({$_ <= $max and $_ > 1}).unique;
    my @powers;
    for @factors -> $div {
        for 2..* -> $exp {
            last if $div ^ $exp > $n;
            push @powers, "$div ^ $exp" if $div ** $exp == $n;
        }
    }
    return @powers;
}

sub MAIN (Int $n is copy where $n > 1) {
    my @pow = find-powers $n;
    say 0 if @pow.elems == 0;
    .say for @pow;
}

These are some results for various input values:

$ perl6 power-integer.p6 125
5 ^ 3

$ perl6 power-integer.p6 128
2 ^ 7

$ perl6 power-integer.p6 64
2 ^ 6
4 ^ 3
8 ^ 2

$ perl6 power-integer.p6 256
2 ^ 8
4 ^ 4
16 ^ 2

$ perl6 power-integer.p6 9
3 ^ 2

$ perl6 power-integer.p6 45
0

Wrapping up

The next week Perl Weekly Challenge is due to 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 Sunday, July 5, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.

Leave a comment

About laurent_r

user-pic I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.