The Weekly Challenge 261

Element Digit Sum & Multiply by Two: Digit Sum Difference and Repeated Doubling in Perl & Python

Lubos Kolouch March 17, 2024 Challenge Details GitHub Solutions

Task 1: Element Digit Sum

You are given an array of integers, @ints.

Write a script to evaluate the absolute difference between element and digit sum of the given array.

Example 1: Input: @ints = (1, 2, 3, 45) → Output: 36 (Element Sum: 51, Digit Sum: 15, |51 - 15| = 36)

Example 2: Input: @ints = (1, 12, 3) → Output: 9 (Element Sum: 16, Digit Sum: 7, |16 - 7| = 9)

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

Example 4: Input: @ints = (236, 416, 336, 350) → Output: 1296

Method Explanation

For each integer in @ints, we compute two quantities:

  1. The element sum, which is the sum of all integers in the array.
  2. The digit sum, which is the sum of the base-10 digits across every element in the array.

Finally, we return the absolute difference |element_sum - digit_sum|. This requires a single linear pass over the elements and their decimal representations.

Perl Solution

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

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

sub element_digit_sum ($ints) {
    my $element_sum = 0;
    my $digit_sum   = 0;

    for my $int (@$ints) {
        $element_sum += $int;
        $digit_sum   += $_ for split //, abs($int);
    }

    return abs( $element_sum - $digit_sum );
}

Python Solution

def element_digit_sum(ints: list[int]) -> int:
    """Return the absolute difference between the element sum and digit sum of ints."""
    element_sum = sum(ints)
    digit_sum = sum(int(c) for n in ints for c in str(abs(n)))
    return abs(element_sum - digit_sum)

Task 2: Multiply by Two

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

Write a script to do the following:

  • a) Look for $start in the array @ints, if found multiply the number by 2
  • b) If not found stop the process, otherwise repeat

In the end return the final value.

Example 1: Input: @ints = (5, 3, 6, 1, 12), $start = 3 → Output: 24

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

Example 3: Input: @ints = (5, 6, 7), $start = 2 → Output: 2

Method Explanation

To avoid scanning the array repeatedly in $O(N)$ time on each step:

  1. Insert all elements of @ints into a hash set (a Perl hash %seen or Python set) in $O(N)$ time.
  2. While $start is present in the set, double $start ($start *= 2).
  3. Return $start once it is no longer found in the set.

Each membership check is $O(1)$, yielding an overall time complexity of $O(N)$ and space complexity of $O(N)$.

Perl Solution

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

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

sub multiply_by_two ( $ints, $start ) {
    my %seen = map { $_ => 1 } @$ints;

    while ( $seen{$start} ) {
        $start *= 2;
    }

    return $start;
}

Python Solution

def multiply_by_two(ints: list[int], start: int) -> int:
    """Repeatedly multiply start by 2 while it is present in ints."""
    ints_set = set(ints)

    while start in ints_set:
        start *= 2

    return start