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 != $j0 <= ($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:
- If
num == 0:2 * 0 = 0, so a double exists if and only if zero was already seen in a prior index. - If
num != 0: Does our set already contain2 * num(meaning the current number is the half), or isnumeven and does the set containnum / 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