The Weekly Challenge 290

Double Exist & Luhn's Algorithm: Practical Lookups and Validation

Lubos Kolouch October 14, 2024 Challenge Details GitHub Solutions

Task 1: Double Exist

You are given an array of integers, @ints.

Write a script to determine if there exist two indices $i and $j such that:

  • $i != $j
  • 0 <= ($i, $j) < scalar @ints
  • $ints[$i] == 2 * $ints[$j]

Method Explanation

A naive brute-force comparison checks all pairs (i, j) in $O(n^2)$ time. However, by using a hash set (or dictionary) of previously seen numbers, we can solve this problem in linear time $O(n)$ with a single pass.

For each number num in the list, we check:

  1. If num == 0: 2 * 0 = 0, so a double exists if and only if zero was already seen in a prior index.
  2. If num != 0: Does our set already contain 2 * num (meaning the current number is the half), or is num even and does the set contain num / 2 (meaning the current number is the double)?

If either condition holds, we immediately return true. Otherwise, we add num to our set of seen numbers and proceed.

Perl Solution

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

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

sub double_exist ($ints_ref) {
    my %seen;
    foreach my $num (@$ints_ref) {
        if ($num == 0) {
            return 'true' if $seen{0};
        } else {
            return 'true' if exists $seen{$num * 2} || ($num % 2 == 0 && exists $seen{$num / 2});
        }
        $seen{$num} = 1;
    }
    return 'false';
}

Python Solution

def double_exist(ints: list[int]) -> bool:
    seen: set[int] = set()
    for num in ints:
        if num == 0:
            if 0 in seen:
                return True
        else:
            if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
                return True
        seen.add(num)
    return False

Task 2: Luhn's Algorithm

You are given a string containing digits and possibly spaces or separators.

Write a script to validate the string using Luhn's Algorithm:

  1. Extract all digits from the input string.
  2. Treat the last digit as the payload (check digit).
  3. From right to left (excluding the check digit), double every other digit.
  4. If doubling a digit results in a number greater than 9, subtract 9.
  5. Sum all the transformed digits.
  6. Compute the expected check digit: (10 - (sum % 10)) % 10.
  7. Verify whether the check digit matches the payload.

Method Explanation

Luhn's algorithm (or the "modulus 10" algorithm) is widely used in credit card and identification number validation to guard against accidental typing errors.

The implementation involves extracting digit characters using regular expressions (/\d/g in Perl or re.findall(r"\d", s) in Python). If fewer than 2 digits exist, validation fails. We pop the check digit, reverse the remaining digits to make 0-indexed right-to-left processing straightforward, double the digits at even indices (index 0, 2, 4...), subtract 9 if greater than 9, sum the total, and compare against the expected check digit.

Perl Solution

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

signature_for luhn_algorithm => (
    method => 0,
    positional => [ Str ],
);

sub luhn_algorithm ($str) {
    my @digits = $str =~ /(\d)/g;
    return 'false' if @digits < 2;

    my $payload = pop @digits;
    my @reversed_digits = reverse @digits;

    my $sum = 0;
    for my $i (0 .. $#reversed_digits) {
        my $digit = $reversed_digits[$i];
        if ($i % 2 == 0) {
            $digit *= 2;
            $digit -= 9 if $digit > 9;
        }
        $sum += $digit;
    }

    my $correct_check_digit = (10 - ($sum % 10)) % 10;
    return $payload == $correct_check_digit ? 'true' : 'false';
}

Python Solution

import re

def luhn_algorithm(s: str) -> bool:
    digits = [int(d) for d in re.findall(r"\d", s)]
    if len(digits) < 2:
        return False

    payload = digits.pop()
    digits.reverse()

    for i in range(len(digits)):
        if i % 2 == 0:
            digits[i] *= 2
            if digits[i] > 9:
                digits[i] -= 9

    sum_digits = sum(digits)
    correct_check_digit = (10 - (sum_digits % 10)) % 10

    return payload == correct_check_digit