Doubled Pairs

October 20, 2020

Let’s start with the student’s quadratic solution; we solve only the extra-extra credit problem, because given that, the others are trivial:

(define (g xs)
  (list-of (list y z)
    (y in xs)
    (z in xs)
    (= (+ y y) z)))
> (g '(1 2 3 4))
((1 2) (2 4))
> (g '(1 3 5 7 9))
()

For the linear solution, we use sets implemented using hash tables; the first do inserts each item into a set, the second do finds the doubles:

(define (f xs)
  (let ((ht (make-eq-hashtable)) (zs (list)))
    (do ((xs xs (cdr xs))) ((null? xs))
      (hashtable-set! ht (car xs) (car xs)))
    (do ((xs xs (cdr xs))) ((null? xs) zs)
     (when (hashtable-contains? ht (* (car xs) 2))
           (set! zs (cons (list (car xs) (* (car xs) 2)) zs)))))))
> (f '(1 2 3 4))
((2 4) (1 2))
> (f '(1 3 5 7 9))
()

You can run the program at https://ideone.com/BXXc5i.

Pages: 1 2

12 Responses to “Doubled Pairs”

  1. James Curtis-Smith said

    Not 100% sure this is O(n) – as hash look up I think is probably O(log(n)), so I think it would be O(n log(n));

    foreach(@ARGV) {
      print $_/2,",$_\n" if exists $X{$_/2};
      print "$_,",$_*2,"\n" if exists $X{2*$_};
      $X{$_}++;
    }
    

    You could use a sparse array [as numbers all +ve] which would be O(n) as array look up would O(1).

    my $m = 0;
    foreach (@ARGV) {
      $m = $_ if $_>$m;
    }
    $X[ $m ] = 0;
    foreach(@ARGV) {
      print $_/2,",$_\n" if !($_%2) && $X[ $_/2 ];
      print "$_,",$_*2,"\n" if $X[ 2*$_ ];
      $X[ $_ ] = 1;
    }
    
  2. matthew said

    I’m not sure you can do this in O(n) time, without considering hash lookup as constant time. If the input array is sorted (like the examples), then scanning through with two pointers (one for n, one for 2n) would work well.

  3. programmingpraxis said

    Yes, I am assuming hash lookup is O(1). At worst, you could use some sort of balanced tree and solve the problem in guaranteed O(n log n) time. And it is not fair to assume the input is sorted, but if you sort first, in time O(n log n), then you could scan the input in O(n). Actually, since the input is positive integers, you could use some sort of counting sort or radix sort in O(n) time, giving a complete solution in O(n) time. But I’m pretty sure the instructor was looking for a hash table solution.

  4. Daniel said

    Here are two solutions in Python. The first approach uses a hash set. The second approach uses a bitwise trie to work around the superlinear worst-case runtime of hashing.

    from typing import Iterable
    
    def doubled_pairs_hash(items: Iterable):
        s = set(items)
        yield from ((x, x * 2) for x in items if x * 2 in s)
    
    def doubled_pairs_trie(items: Iterable):
        # Node format: [<LEFT_BRANCH>, <RIGHT_BRANCH>, <IS_MEMBER>]
        trie = [[], [], False]
        # Fill trie
        for x in items:
            node = trie
            while x:
                node = node[x & 1]
                if not node:
                    node.extend(([], [], False))
                x >>= 1
            node[2] = True
        # Search trie
        for x in items:
            y = 2 * x
            node = trie
            while y and node:
                node = node[y & 1]
                y >>= 1
            else:
                if node and node[2]:
                    yield x, 2 * x
    
    for pair in doubled_pairs_hash(range(1, 8)):
        print(pair)
    
    for pair in doubled_pairs_trie(range(1, 8)):
        print(pair)
    

    Output:

    (1, 2)
    (2, 4)
    (3, 6)
    (1, 2)
    (2, 4)
    (3, 6)
    
  5. Daniel said

    “the superlinear worst-case runtime of hashing.” -> “the superlinear worst-case runtime of hash lookup”.

  6. Daniel said

    The while/else loop was a mistake in my prior trie-based solution, as I switched away from using a break statement. Here’s the updated function, which no longer uses while/else.

    def doubled_pairs_trie(items: Iterable):
        # Node format: [<LEFT_BRANCH>, <RIGHT_BRANCH>, <IS_MEMBER>]
        trie = [[], [], False]
        # Fill trie
        for x in items:
            node = trie
            while x:
                node = node[x & 1]
                if not node:
                    node.extend(([], [], False))
                x >>= 1
            node[2] = True
        # Search trie
        for x in items:
            y = 2 * x
            node = trie
            while y and node:
                node = node[y & 1]
                y >>= 1
            if y == 0 and node and node[2]:
                yield x, 2 * x
    
  7. Zack said

    Here is my take on this in Julia: https://pastebin.com/Cs3m5jVM
    Not sure if this qualifies as linear time, but it certainly is much faster than the quadratic time solution.
    Cheers!

  8. mvaneerde said

    find_doubles(int size, int *array) {
    // create two indexes i and j
    // start both indexes at the beginning
    int i = 0;
    int j = 0;

    bool done = false;
    while (!done) {
        // advance the SECOND index until array[j] >= 2 * array[i]
        while ((j < size) && (array[j] < 2 * array[i])) {
            j++;
        }
    
        if (j == size) {
            // we found all the pairs!
            done = true;
            break;
        }
    
        // if the >= is an == we found a pair
        if (array[j] == 2 * array[i]) {
            LOG("(%d, %d)", array[i], array[j]);
        }
    
        // advance the FIRST index by one
    }
    

    }

  9. mvaneerde said

    oops missing an i++; after that last comment

  10. matthew said

    Here’s a Haskell one-liner: ‘ap’ in the function monad is the S-combinator, so that ‘ap f g x’ is the same as ‘f x (g x)’. The result is just the list of doubled elements:

    Prelude> import Data.List.Ordered
    Prelude Data.List.Ordered> import Control.Monad
    Prelude Data.List.Ordered Control.Monad> f = ap isect (map (*2)) . sort
    Prelude Data.List.Ordered Control.Monad> f [6,2,3,7,1,4]
    [2,4,6]
    
  11. Jigar Moradiya said

    I have achieved this using JS with simple includes function:

    let list = [1,2,3,4,6]
    let [isDoubleExists, pairs] = getPairs(list)
    console.log(isDoubleExists,pairs)

    function getPairs(listInput) {
    let resPairs = []
    list.forEach(item=>{
    if (list.includes(item2)){
    resPairs.push([item,item
    2])
    }
    })
    if (resPairs.length > 0 ) {
    return [true, resPairs]
    } else {
    return [false,resPairs]
    }
    }

  12. Mitchell said

    (defun contains-double (seq)
    (remove-if #’null
    (map ‘list
    (lambda (x)
    (let ((double (find (* 2 x) seq)))
    (when double
    (cons x double))))
    seq)))
    (defun contains-double (seq)
    (remove-if #’null
    (map ‘list
    (lambda (x)
    (let ((double (find (* 2 x) seq)))
    (when double
    (cons x double))))
    seq)))

    (contains-double #(8 1 2 3 4 5 6 7 10 20))
    ;;=> ((1 . 2) (2 . 4) (3 . 6) (4 . 8) (5 . 10) (10 . 20))

    Here is my common lisp attempt. I’m not sure how to verify its time complexity though

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

%d bloggers like this: