Task 1: 3-Sum
Given an array and a target, find all unique triplets in the array that sum to the target.
Example Output
Input: target = 0, list = [-25, -10, -7, -3, 2, 4, 8, 10]
Output: [-10, 2, 8] [-7, -3, 10]
Logic
Sort the array. Fix the first element list[i], and then use two pointers (left starting at i+1 and right at the end of the list) to search for pairs that sum to target - list[i].
Perl Solution
ch-1.pl
sub find_unique_triplets {
my ( $target, @list ) = @_;
@list = sort { $a <=> $b } @list;
my @triplets;
my $len = scalar @list;
for ( my $i = 0 ; $i < $len - 2 ; $i++ ) {
my $left = $i + 1;
my $right = $len - 1;
while ( $left < $right ) {
my $sum = $list[$i] + $list[$left] + $list[$right];
if ( $sum == $target ) {
push @triplets, [ $list[$i], $list[$left], $list[$right] ];
$left++; $right--;
}
elsif ( $sum < $target ) { $left++; }
else { $right--; }
}
}
return \@triplets;
}
Python Solution
ch-1.py
def find_unique_triplets(target: int, lst: List[int]) -> List[Tuple[int, int, int]]:
lst.sort()
triplets = []
length = len(lst)
for i in range(length - 2):
left = i + 1
right = length - 1
while left < right:
s = lst[i] + lst[left] + lst[right]
if s == target:
triplets.append((lst[i], lst[left], lst[right]))
left += 1; right -= 1
elif s < target:
left += 1
else:
right -= 1
return triplets
Task 2: Colorful Numbers
Find if a given number is a Colorful Number. A colorful number is a number where all the products of consecutive subsets of digits are different.
Example Output
263 is colorful (products: 2, 6, 3, 12, 18, 36 are all unique)
236 is not colorful (products of subset 2*3 = 6, which duplicates digit 6)
Logic
Generate all contiguous subarrays of digits of the number. Calculate the product of digits for each subarray and insert it into a set. If any product is already present in the set, the number is not colorful.
Perl Solution
ch-2.pl
sub is_colorful {
my $number = shift;
my %products;
my @digits = split //, $number;
my $len = scalar @digits;
for ( my $i = 0 ; $i < $len ; $i++ ) {
my $product = 1;
for ( my $j = $i ; $j < $len ; $j++ ) {
$product *= $digits[$j];
return 0 if exists $products{$product};
$products{$product} = 1;
}
}
return 1;
}
Python Solution
ch-2.py
def is_colorful(number: int) -> bool:
products = set()
digits = [int(d) for d in str(number)]
length = len(digits)
for i in range(length):
product = 1
for j in range(i, length):
product *= digits[j]
if product in products:
return False
products.add(product)
return True