The Weekly Challenge 051

3-Sum and Colorful Numbers

Solutions on GitHub

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