The Problem

An extremely simple problem to kick things off, and one that shows up on many beginners programming tests: find two numbers from a list that add up to a specified number. Part 2 asks for three numbers that add up to the specified number. The list is not sorted.

My Solution

My solution was pretty obvious: sort the list, and do a binary search. However, turns out that NumPy has a pretty nice function called searchsorted. We give it the sorted list and a list of keys to search for, and it returns a list of indices, each corresponding to where the key would be inserted while maintaining the order. So pretty cool, I learnt about a new function. And my overall runtime is $O(n\lg{n})$

For Part 2, the natural approach is to repeat part 1 for every element of the list, while suitably modifying the desired sum.

Other Approaches

Now the fun part! Let’s order these into three groups

Algorithm

  • The straightforward – a doubly nested loop,  $O(n^2)$
  • Many binary searches; see the next section for variations in the implementation
  • The one I liked best, and one that I’m kicking myself for not thinking about. Set a lo and hi index and add the corresponding values. If the sum is greater than the desired value, decrement hi, if less, increment lo, if equal, we’re done. The proof of why this is correct is left to the reader. Note that this only speeds up the search time to linear from  $O(n\lg{n})$, the sorting time is not changed. The asymptotic time for both approaches is the same, but this is more elegant!
  • Generating functions (see below)

Implementation

  • The straightforward approach can be expressed as a list comprehension
  • Use recursion to make it generic: if we want  $n$ numbers that add up to the desired value, express this in terms of $n-1$. And of course, don’t forget to terminate the recursion
  • Read the list of numbers into a set. Offload the search for the second number to the set. This can be done using a list as well, but the search time will be linear instead of logarithmic. Another approach used two dicts, for each input number and its complement. I think this was overkill, though I liked the approach
  • itertools.combinations I need to get a better handle on the itertools library. Turns out we can simply create all 2-combinations and a loop over these is all that is required. I haven’t looked up the time complexity, but this is likely  $O(n^2)$, so there is that…
  • itertools.product also can be used for generating the cartesian products of the input

Yowza!!

Express the input list as a polynomial. The values of the list are coefficients and the powers of the variable. Then in the square of this polynomial, the coefficient of the target numbered term is the product that we’re looking for since powers are added and coefficients are multiplied. Knuth would approve!! And of course, we can do the polynomial multiplication using FFTs.

Follow by Email
Facebook
Twitter
LinkedIn

Leave a comment

Your email address will not be published. Required fields are marked *

Search

  • Search

  • Categories

  • Post Date