The Weekly Challenge 066

Divide Integers and Power Integers

Solutions on GitHub

Task 1: Divide Integers

Divide two integers M and N without using multiplication, division, or modulo operator.

Example Output

Input: M = 25, N = 3 Output: 8

Logic

Use bitwise left shifts to subtract exponentially larger multiples of N from M, building up the quotient.

Perl Solution

ch-1.pl

sub divide { my ($M, $N) = @_; my $sign = (($M < 0) ^ ($N < 0)) ? -1 : 1; my $abs_M = abs($M); my $abs_N = abs($N); my $quotient = 0; while ($abs_M >= $abs_N) { my $temp = $abs_N; my $multiple = 1; while ($abs_M >= ($temp << 1)) { $temp <<= 1; $multiple <<= 1; } $abs_M -= $temp; $quotient += $multiple; } return $sign * $quotient; }

Python Solution

ch-1.py

def divide(M: int, N: int) -> int: sign = -1 if (M < 0) ^ (N < 0) else 1 abs_M, abs_N = abs(M), abs(N) quotient = 0 while abs_M >= abs_N: temp, multiple = abs_N, 1 while abs_M >= (temp << 1): temp <<= 1 multiple <<= 1 abs_M -= temp quotient += multiple return sign * quotient

Task 2: Power Integers

Check if an integer N can be expressed as m^n for integers m >= 2 and n >= 2.

Example Output

Input: 64 Output: True (2^6, 4^3, 8^2)

Logic

Iterate base m from 2 up to sqrt(N) and power n from 2 up to log_m(N). Check if m^n == N.

Perl Solution

ch-2.pl

sub find_expressions { my ($N) = @_; my @solutions; for my $m (2 .. sqrt($N)) { for my $n (2 .. int(log($N)/log($m) + 1e-9)) { push @solutions, "$m^$n" if ($m ** $n) == $N; } } return @solutions; }

Python Solution

ch-2.py

def is_power_integer(N: int) -> bool: if N < 4: return False for m in range(2, int(N**0.5) + 1): p = m * m while p <= N: if p == N: return True p *= m return False