Task 1: Middle Index
You are given an array of integers, @ints. Write a script to find the leftmost index where the sum of numbers to its left equals the sum of numbers to its right. If no such index exists, return -1.
Method Explanation
A naive recalculation of left and right sums for each index takes quadratic $O(N^2)$ time. Instead, we can solve this in linear $O(N)$ time and $O(1)$ extra space:
- Compute the
total_sumof all elements in the array. - Maintain a running
left_sum(initially 0). - For each index $i$, the sum of elements strictly to its right is: $$\text{right\_sum} = \text{total\_sum} - \text{left\_sum} - \text{ints}[i]$$
- If
left_sum == right_sum, return the current index $i$ immediately (guaranteeing the leftmost match). - Otherwise, update
left_sum += ints[i]and proceed.
Perl Implementation
sub find_middle_index ($ints) {
($ints) = $INTS_CHECK->($ints);
return -1 if !@$ints;
my $total_sum = 0;
$total_sum += $_ for @$ints;
my $left_sum = 0;
for my $i ( 0 .. $#$ints ) {
my $right_sum = $total_sum - $left_sum - $ints->[$i];
if ( $left_sum == $right_sum ) {
return $i;
}
$left_sum += $ints->[$i];
}
return -1;
}
Python Implementation
def find_middle_index(ints: Sequence[int]) -> int:
"""Find the leftmost index where sum of left elements equals sum of right elements."""
total_sum = sum(ints)
left_sum = 0
for i, val in enumerate(ints):
right_sum = total_sum - left_sum - val
if left_sum == right_sum:
return i
left_sum += val
return -1
Task 2: Poker Hand Rankings
A draw poker hand consists of 5 cards, drawn from a pack of 52 cards (no jokers, no wild cards; Ace ranks high or low). Determine:
- How many different 5-card hands can be dealt?
- How many different hands of each of the 10 ranks can be dealt?
- Verify the sum of the 10 rank counts equals the total number of hands.
Combinatorial Derivation
The total number of 5-card hands is $\binom{52}{5} = 2,598,960$. The 10 mutually exclusive categories are calculated as follows:
- Royal Flush: 4 suits $\times 1 = 4$.
- Straight Flush: 9 sequences (A-2-3-4-5 up to 9-10-J-Q-K) $\times 4\text{ suits} = 36$.
- Four of a Kind: $\binom{13}{1} \times \binom{4}{4} \times \binom{48}{1} = 13 \times 1 \times 48 = 624$.
- Full House: $\binom{13}{1} \times \binom{4}{3} \times \binom{12}{1} \times \binom{4}{2} = 13 \times 4 \times 12 \times 6 = 3,744$.
- Flush: $4 \times \binom{13}{5} - \text{Royal} - \text{Straight Flush} = 5,148 - 40 = 5,108$.
- Straight: $10 \times 4^5 - \text{Royal} - \text{Straight Flush} = 10,240 - 40 = 10,200$.
- Three of a Kind: $\binom{13}{1} \times \binom{4}{3} \times \binom{12}{2} \times 4^2 = 13 \times 4 \times 66 \times 16 = 54,912$.
- Two Pair: $\binom{13}{2} \times \binom{4}{2}^2 \times \binom{11}{1} \times 4 = 78 \times 36 \times 11 \times 4 = 123,552$.
- One Pair: $\binom{13}{1} \times \binom{4}{2} \times \binom{12}{3} \times 4^3 = 13 \times 6 \times 220 \times 64 = 1,098,240$.
- High Card: Total minus all above $= 1,302,540$.
Sum of all 10 hand ranks $= 4 + 36 + 624 + 3744 + 5108 + 10200 + 54912 + 123552 + 1098240 + 1302540 = 2,598,960$.
Perl Implementation
sub calculate_poker_hands () {
my $total_hands = nCr( 52, 5 );
my %counts;
$counts{'Royal Flush'} = Math::BigInt->new(4);
$counts{'Straight Flush'} = Math::BigInt->new( 9 * 4 );
$counts{'Four of a Kind'} = Math::BigInt->new(13)->bmul( nCr( 48, 1 ) );
$counts{'Full House'} = Math::BigInt->new(13)->bmul( nCr( 4, 3 ) )->bmul(12)->bmul( nCr( 4, 2 ) );
my $all_flushes = Math::BigInt->new(4)->bmul( nCr( 13, 5 ) );
$counts{'Flush'} = $all_flushes->bsub( $counts{'Royal Flush'} )->bsub( $counts{'Straight Flush'} );
my $all_straights = Math::BigInt->new(10)->bmul( Math::BigInt->new(4)->bpow(5) );
$counts{'Straight'} = $all_straights->bsub( $counts{'Royal Flush'} )->bsub( $counts{'Straight Flush'} );
$counts{'Three of a Kind'} = Math::BigInt->new(13)->bmul( nCr( 4, 3 ) )->bmul( nCr( 12, 2 ) )->bmul( Math::BigInt->new(4)->bpow(2) );
$counts{'Two Pair'} = nCr( 13, 2 )->bmul( nCr( 4, 2 )->bpow(2) )->bmul(11)->bmul(4);
$counts{'One Pair'} = Math::BigInt->new(13)->bmul( nCr( 4, 2 ) )->bmul( nCr( 12, 3 ) )->bmul( Math::BigInt->new(4)->bpow(3) );
my $sum_non_high = Math::BigInt->new(0);
$sum_non_high->badd( $counts{$_} ) for keys %counts;
$counts{'High Card'} = Math::BigInt->new($total_hands)->bsub($sum_non_high);
return ( $total_hands, \%counts );
}
Python Implementation
def calculate_poker_hands() -> tuple[int, dict[str, int]]:
"""Calculate the total number of 5-card hands and frequency of each poker rank."""
total_hands = nCr(52, 5)
counts: dict[str, int] = {}
counts["Royal Flush"] = 4
counts["Straight Flush"] = 9 * 4
counts["Four of a Kind"] = 13 * nCr(48, 1)
counts["Full House"] = 13 * nCr(4, 3) * 12 * nCr(4, 2)
total_flushes = 4 * nCr(13, 5)
counts["Flush"] = total_flushes - counts["Royal Flush"] - counts["Straight Flush"]
total_straights = 10 * (4**5)
counts["Straight"] = total_straights - counts["Royal Flush"] - counts["Straight Flush"]
counts["Three of a Kind"] = 13 * nCr(4, 3) * nCr(12, 2) * (4**2)
counts["Two Pair"] = nCr(13, 2) * (nCr(4, 2) ** 2) * 11 * 4
counts["One Pair"] = 13 * nCr(4, 2) * nCr(12, 3) * (4**3)
sum_other = sum(counts.values())
counts["High Card"] = total_hands - sum_other
return total_hands, counts