Doubled Pairs
October 20, 2020
Today’s exercise is somebody’s homework problem:
You are given an array containing positive integers, all distinct. Write a program that determines if there exist in the array any numbers such that one is double the other. For instance, in the array [1,2,3,4], the pairs 1,2 and 2,4 are both doubles, so the program should return True; in the array [1,3,5,7,9] there is no such doubled pair, so the program should return False. For extra credit, return a pair that proves the result is True, if it exists. For extra-extra credit, return all such pairs. Your program must run in linear time.
The student who asked for help realized there was a simple nested-loop solution that runs in quadratic time, but that doesn’t meet the constraints of the homework problem.
Your task is to solve all three levels of the homework problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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; }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.
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.
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:
“the superlinear worst-case runtime of hashing.” -> “the superlinear worst-case runtime of hash lookup”.
The
while/elseloop was a mistake in my prior trie-based solution, as I switched away from using abreakstatement. Here’s the updated function, which no longer useswhile/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 * xHere 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!
find_doubles(int size, int *array) {
// create two indexes i and j
// start both indexes at the beginning
int i = 0;
int j = 0;
}
oops missing an i++; after that last comment
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:
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,item2])
}
})
if (resPairs.length > 0 ) {
return [true, resPairs]
} else {
return [false,resPairs]
}
}
(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