Perl Weekly Challenge 86, Part 1

You are given an array of integers @N and an integer $A.

Write a script to find find if there exists a pair of elements in the array whose difference is $A.

Print 1 if exists otherwise 0.

That’s a pretty simple task. We could just have two nested loops over the array @N, and for each pair, subtract the elements and see if they equal $A. Simple, but inefficient. There are \Omega (N^2) pairs of elements, leading to a quadratic runtime behaviour of the resulting program.

We can do much better. If we have an integer $n which is in the array @N, instead of scanning through @N different integer $m such that $n - $m == $A we could also ask is there an integer $n - $A in @N. And with a bit of preprocessing, that question is easily answered.

Perl

Using Perl, we can store the numbers in a hash, and then do lookup in (expected) constant time, leading to a linear time (expected) algorithm.

In the program below, we assume an even number of input lines; with every pair of lines giving us an instance of the challenge. Odd lines will have a sequence of integers (the array @N in the stated challenge), even lines will have the difference ($A in the stated challenge).

LINE: while (!eof ()) {
    #
    # Read data:
    #   odd  lines are the numbers in @N
    #   even lines are the differences ($A).
    #
    my %data;
    $data {$_} ++ for <> =~ /[0-9]+/g;
    last if eof ();
    chomp (my $diff = <>);

    foreach my $number (keys %data) {
        my $target = $number - $diff;
        if ($data {$target} && ($diff || $data {$number} > 1)) {
            say 1;
            next LINE;
        }
    }

    say 0;
}

We first read in a line, extract the integers from it and store this in the hash %data. We also count how often the integer occurs in the input. A second line is read to record the wanted difference ($diff).

We then loop over the keys of the hash %data, these are our input numbers. We calculate which number we are looking for ($target = $number - $diff), and check whether it exist in the hash (if ($data {$target})). But there is a catch, if the difference is 0, we must make sure the number appears at least twice in the array, or we would be subtracting a number with itself and get a false positive.

If we find the right number, we print 1, and move on to the next challenge. Else, we continue checking the next number. If we don’t find a correct pair, we print 0, and move on to the next challenge.

The complete program can be found on GitHub.

Node.js

Our solution for Node.js is similar to our Perl solution. We use an object to store the data numbers, so we can quickly check whether a specific number exists.

Reading in the data is a bit different than in Perl:

// Read STDIN. Split on newlines, then on whitespace, and 
// turn the results into numbers. Since the input will be
// newline terminated, we have an empty line to filter out.
let lines = require      ("fs")
          . readFileSync (0)          // Read all.
          . toString     ()           // Turn it into a string.
          . split        ("\n");      // Split on newlines.

// Iterate pair wise over the lines
for (let i = 0; i < lines . length - 1; i += 2) {
    // First line is a set of integers, split on
    // white space, and store the numbers in a hash.
    let data = lines [i] . split  (" ")
                         . reduce ((acc, val) => {
        acc [val] = acc [val] ? acc [val] + 1 : 1;
        return acc;
    }, {});

    // Second line is the target difference
    let diff = +lines [i + 1];

    ...
}

We read everything from STDIN, and split it on newlines, storing the lines into the array lines.

We then loop over lines, processing two lines at a time. The first line contains the set of numbers: we split the line on white space, then we iterate over the parts, putting them into an object named data: the keys of the object are the different numbers in the input, the values count how often the corresponding number appears in the input.

The second line stores the target difference into diff: the unary + numifies the string.

Checking for winning pairs is now easy, and works the same way as the Perl solution:

// For each number in the array, check whether there is
// another number so their difference is that target
// difference. Special care has to be taken if the target
// difference is 0.
let winner = 0;
Object . keys (data) . forEach ((number) => {
    if (!winner) {
        let target = number - diff;
        if (data [target] && (diff || data [target] > 1)) {
            winner = 1;
        }
    }
});
console . log (winner);

The complete program can be found on GitHub.

C

C does not have native hashes, or anything like that. So, our attack is going to be a bit different. We still will have just one loop, but we are using binary search to find whether there is another number so their difference equals the given difference. Luckily, last week we needed a binary search as well, so we can modify this.

# include <stdbool.h>
/* Binary search: return true if target is in array,
 * with index i, min <= i < max. */
bool bin_search (long * array, long target, size_t min, size_t max) {
    size_t mid = (min + max) / 2;   /* In C, dividing integers yields an *
                                     * integer, so there is no need for  *
                                     * flooring.                         */

    return min >= max            ? false
         : array [mid] == target ? true
         : array [mid] >  target ?
                     bin_search (array, target, min,     mid)
         :           bin_search (array, target, mid + 1, max);
}

This is a standard implementation of binary search. A single call takes O (\log N) time, where N is the number of elements in array (or rather, max - min).

To do a binary search, the array must be sorted. Luckily, C comes with a quick sort method qsort. One of the arguments of qsort is a function which compares two elements, and whose return values perform the same role as the code block of the first argument to sort in Perl. We are using the following code to sort the array, which at that point contains the input numbers:

/* Compare two integer values, returning -1, 0, 1 if the first
 * is smaller, equal, or larger than the second. */
int cmp (const void * a, const void * b) {
    long diff = * (long *) a - * (long *) b;
    return  diff < 0 ? -1
         :  diff > 0 ?  1
         :              0;
}

qsort (array, size, sizeof (long), cmp);

Here, cmp takes pointers to two values (in this case, two longs). -1 is returned if the first number is the smaller, 0 if they are equal, and 1 if the second number is larger. array contains size number (of type long). The expected run time of qsort is O (N \log N) where N is the number of elements in the array to be sorted.

Now, let us focus on reading the input. We have to work a lot harder than with Perl! We have to do our own memory management, allocating more memory to an array if it grows. And we have to scan lines of input. Here’s how we read the array of numbers:

# define DEFAULT_BUF_SIZE  128
# define BUF_INCREMENT       1.25

/* Declare an array, and give it some memory. */
long * array    = NULL;
size_t buf_size = DEFAULT_BUF_SIZE;
if (array = (long *) malloc (buf_size * sizeof (long))) == NULL) {
    fprintf (stderr, "Out of memory\n");
    return (1);
}

/* Arguments to getline () */
char *  line = NULL;  /* Pointer to line we read in */
size_t  len  = 0;     /* Number of characters read  */

if (getline (&line, &len, stdin) != -1) {
    int    offset;
    char * line_ptr = line;

    while (sscanf (line_ptr, "%ld%n", &input, &offset) == 1) {
        line_ptr += offset;

        if (++ size >= buf_size) {
            /* Get some more memory. */
            buf_size = (size_t) floorf (buf_size * BUF_INCREMENT);
            if ((array = (long *) realloc (array,
                         buf_size * sizeof (long))) == NULL) {
                fprintf (stderr, "Out of memory\n");
                return (1);
            }
        }

        /* Store it */
        array [size - 1] = input;
    }
}

The function getline reads a line (standard input in our case), and puts the result in line. getline will allocate the memory needed for line. len will be updated to show how much was allocated.

We’re then using sscanf to read long integers. line_ptr points to from where we’re scanning a long integer, which we’re updating each time we’ve scanned a number. Since sscanf sets how many characters it scanned in offset, updating line_ptr is easy. The scanned number will be put input.

We then want to store input in array. But if we have reached the end of the allocated memory of the array, we have to use realloc to increase the buffer size. Each time, we increase the allocated memory by 25%.

Reading the target difference is easy. We read a line, then use strol to parse an long integer from it. We then take the absolute value using labs:

long target;
if (getline (&line, &len, stdin) != -1) {
    char * endptr;
    target = labs (strtol (line, &endptr, 10));
}

We can now iterate over the array, and for each element array [i], use binary search to see whether there is an element array [i] + target in the array, with some index greater than i. Since all elements with index greater than cannot be less than array [i], this is why we take the absolute value of the target difference. And we also don’t have to special case a target difference of 0: since we’re searching in the array past the index i, any result from the binary search will be from a different index than i:

bool winner = false;
for (size_t i = 0; i < size && !winner; i ++) {
    winner = bin_search (array, target + array [i], i + 1, size);
}
printf ("%d\n", winner ? 1 : 0);

Note that we stop the loop as soon as we have a suitable pair.

The complete program can be found on GitHub.

SQL

For our SQL solution, we need a table, and a query. Our table looks as follows:

CREATE TABLE Numbers (
    id    integer PRIMARY KEY,
    value integer
);

Each number of the input will be stored in a different row in the table. The query looks like:

SELECT  COUNT(*)
  FROM (SELECT  1
          FROM  Numbers t1,
                Numbers t2
         WHERE  t1.id   != t2.id
           AND  t1.value - t2.value = ?
        LIMIT 1)

For the placeholder, the target difference ($A in the stated challenge) is substituted.

The inner query searches for a pair of different numbers whose difference is the wanted difference. For each such pair, a row (with just the value 1) is returned, but since we’re limiting the number of rows to 1, the inner query stops as soon as it finds a hit. The outer query counts the number of returned rows returned from the inner query — so the only possible results are 1 and 0.

The table and query are found on GitHub.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s