No dumb one-liners this week.

You are given an array @N of positive integers (sorted) and another non negative integer k.

Write a script to find if there exists 2 indices i and j such that A[i] - A[j] = k and i != j.

It should print the pairs of indices, if any such pairs exist.

The easiest way to do this is probably with two nested loops. This is the general solution for a given array of numbers, and perhaps the best one at *O(n²)* since you’d have to sum up every two numbers in the array.

With this particular problem, however, we can do better; since we know the array is sorted. We can iterate over the array at *O(n)* and look for a correct number in the array which meets our diff constraint using binary search at *O(log n)*, which gets us down to *O(n log n)*.

Assuming there is a `sub infix:« 🔎 » ($needle, @haystack)`

that returns the index of `$needle`

in `@haystack`

or `Nil`

, the following would print out all the right pairs of indices:

(There are a couple of implementations of binary search in Raku on Rosetta Code.)

```
#!/usr/bin/env raku
my @N = 2, 7, 9;
my $k = 2;
for ^@N -> $i {
my $j = (@N[$i] + $k) 🔎 @N[$i+1..*];
say $i, " ", 1 + $i + $j with $j
}
```

Which operates at *O(log n!)*, which is practically *O(n log n)*.

You are given a binary tree and a sum, write a script to find if the tree has a 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 for a sum.

Here’s the example script:

```
#!/usr/bin/env raku
multi paths(Pair $tree) {
|paths($tree.value).map: {$tree.key, |$_}
}
multi paths(Positional $nodes) {
$nodes.map: { paths $_ }
}
multi paths($leaf) { $leaf }
my $tree = 5 => (4 => 11 => (7, 2),
8 => (9 => 1, 13));
say %(paths($tree).map: {.sum => $_}){22}
```

In the above notation, each parent is the key of a `Pair`

, and its children are the value of that `Pair`

. The variable `$tree`

is therefore a representation of the binary tree below, as came in the text of the task.

`5 / \ 4 8 / / \ 11 13 9 / \ \ 7 2 1`

The `paths`

subroutine returns a list of all the paths in the tree, obviously. When its argument is a single leaf at the bottom of the tree, it act as the identity function. When its argument is a list of nodes, it returns a list of all the paths for each node, recursively calling `paths`

. For arguments in form of a `Pair`

, i.e. a parent and its child(ren) … well … you know what happens.

Note that we use `|`

to flatten the list of different paths because of the function’s recursive nature. Without it, `paths $tree`

would give the following abstract:

```
((5 ((4 (11 7)) (4 (11 2)))) (5 ((8 ((9 1))) (8 13))))
```

Which is sort of correct, but makes calculating the sums harder.

The final statement maps every possible *path sum* in the tree to the path that produces it, hence the program will say:

```
(5 4 11 2)
```

If we asked for 21 instead of 22, it would say:

```
(Any)
```

Which means no path in the binary tree has a sum of 21.