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 