The Weekly Challenge 056

Diff-K and Path Sum

Solutions on GitHub

Task 1: Diff-K

You are given a sorted array @N of positive integers and a non-negative integer k. Write a script to find if there exist 2 indices i and j such that A[j] - A[i] = k and i != j. Print pairs of indices if any such pairs exist.

Example Output

Input: k = 2, arr = [2, 7, 9] Output: (2,1) Input: k = 2, arr = [2, 4, 6] Output: (1,0)(2,1)

Logic

Iterate through the array with a left index i and advance a right pointer j while the difference A[j] - A[i] is less than k. If the difference equals k, store/print the index pair (j, i).

Perl Solution

ch-1.pl

sub get_valid_pairs { my ($k, @arr) = @_; my $answer; for my $i (0 .. scalar @arr - 2) { my $j = $i + 1; while (($arr[$j] - $arr[$i] < $k) and ($j < scalar @arr - 1)) { $j++; } $answer .= "($j,$i)" if $arr[$j] - $arr[$i] == $k; } return $answer; }

Python Solution

ch-1.py

def get_valid_pairs(k: int, arr: list): answer = '' for i in range(0, len(arr)-1): j = i + 1 while (arr[j] - arr[i] < k) and (j < len(arr) - 1): j += 1 if arr[j] - arr[i] == k: answer += f"({j},{i})" return answer

Task 2: Path Sum

Given a binary tree and a target sum, write a script to find if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered.

Example Output

Tree with root 5 and target sum 22: Path found: 5 -> 4 -> 11 -> 2 (Sum: 22)

Logic

Represent the tree using a directed graph structure. Identify all leaf nodes (exterior / external vertices with out-degree 0) and find paths from the root to each leaf. Sum the node values along each path and output paths matching the target sum.

Perl Solution

ch-2.pl

use Graph::Directed; use List::Util qw/sum/; my $g = Graph::Directed->new; $g->add_edge(5,4); $g->add_edge(4,11); $g->add_edge(11,7); $g->add_edge(11,2); $g->add_edge(5,8); $g->add_edge(8,13); $g->add_edge(8,9); $g->add_edge(9,1); my $start = 5; my $sum = 22; for ($g->exterior_vertices) { my @path = $g->SP_Dijkstra($start, $_); say join '->', @path if sum(@path) == $sum; }

Python Solution

ch-2.py

import networkx as nx g = nx.DiGraph() g.add_edge(5, 4); g.add_edge(4, 11); g.add_edge(11, 7); g.add_edge(11, 2) g.add_edge(5, 8); g.add_edge(8, 13); g.add_edge(8, 9); g.add_edge(9, 1) start = 5 my_sum = 22 external_vertices = (x for x in g.nodes() if g.out_degree(x)==0 and g.in_degree(x)==1) for vert in external_vertices: path = nx.shortest_path(g, start, vert) if sum(path) == my_sum: print(path)