The Weekly Challenge 285

Method Explanation

Each route [source, destination] represents a directed edge in a graph. A city with no outgoing connection is a vertex with out-degree $0$ that appears as a destination in at least one route, but never appears as a source.

We can solve this in $O(N)$ time and space using two sets (or hashes):

• Collect all cities that appear first in a route into a sources set.
• Collect all cities that appear second in a route into a destinations set.
• Compute the set difference $\text{destinations} \setminus \text{sources}$ and return the terminal city (or undef / None if the graph forms a cycle).

Perl Solution

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

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

sub find_destination ($routes_ref) {
    my %sources;
    my %destinations;

    for my $route (@$routes_ref) {
        my ( $source, $destination ) = @$route;
        $sources{$source}           = 1;
        $destinations{$destination} = 1;
    }

    for my $city ( sort keys %destinations ) {
        if ( !exists $sources{$city} ) {
            return $city;
        }
    }

    return;
}

Python Solution

from collections.abc import Sequence

def find_destination(routes: Sequence[Sequence[str]]) -> str | None:
    """Find the destination with no further outgoing connection from routes."""
    sources: set[str] = set()
    destinations: set[str] = set()

    for route in routes:
        source, destination = route
        sources.add(source)
        destinations.add(destination)

    no_outgoing = sorted(destinations - sources)
    if no_outgoing:
        return no_outgoing[0]
    return None

Method Explanation

This is the classic Unbounded Knapsack / Coin Change counting problem. Since the order of coins does not matter, we iterate over each coin denomination $c \in \{1, 5, 10, 25, 50\}$ in an outer loop and update a 1D dynamic programming table $\text{dp}[0 \dots \text{amount}]$:

• Initialize $\text{dp}[0] = 1$ (there is exactly 1 way to make 0 cents: using no coins) and $\text{dp}[i] = 0$ for $i > 0$.
• For each coin $c$, iterate $i$ from $c$ to $\text{amount}$ and accumulate $\text{dp}[i] \mathrel{+}= \text{dp}[i - c]$.
• Processing coins in the outer loop guarantees that combinations are counted in canonical coin order, avoiding duplicate permutations.

Perl Solution

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

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

sub making_change ($amount) {
    die 'Amount must be non-negative' if $amount < 0;

    my @coins = ( 1, 5, 10, 25, 50 );
    my @dp    = (0) x ( $amount + 1 );
    $dp[0] = 1;

    for my $coin (@coins) {
        for my $i ( $coin .. $amount ) {
            $dp[$i] += $dp[ $i - $coin ];
        }
    }

    return $dp[$amount];
}

Python Solution

def making_change(amount: int) -> int:
    """Compute the number of ways to make change for the given amount in cents."""
    if amount < 0:
        raise ValueError("Amount must be non-negative")

    coins: tuple[int, ...] = (1, 5, 10, 25, 50)
    dp: list[int] = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]