Thinking about efficiency

This article is going to cover a typical interview test question, which asks you to find the missing number in an array. The array is N elements in size and contains all the numbers 1 to N. The numbers can be in any order but will never repeat. One of the numbers is missing and your task is to find the missing number as efficiently as possible. There are a number of different ways we could tackle this problem, which we’re going to explore. The focus of this article isn’t so much about how to solve this problem and more about the (in)efficiency of different algorithms we might use.

Asymptotic analysis

To compare the differences between the efficiency of each algorithm we’re going to attempt to calculate the asymptotic time complexity. This is a big and fancy word that just means we’ll be evaluating the relative efficiency of each algorithm based on the amount of data input. For example, if we input N items and the algorithm has linear time complexity the asymptotic time will be directly proportional to N. In other words, if N is 10 we know it will take 10 units of time.

The actual units are abstract and all we’re doing is comparing like for like. The unit is just the measure of cost in terms of time but it does not represent seconds, or minutes or hours or, in fact, any specific time at all. The units have no specific meaning other than being comparable with each other.

For example, let’s say I have another algorithm that has a quadratic time complexity and N is 10. The total units of time will be 10^2 (quadratic basically means to the power of two) so I know that for 10 input data it’ll take 100 units of time. Compared to the linear algorithm for the same number of inputs I know that it’ll take 90 more units of time or, put another way, it’s 10 times slower.

There is a good reason the units have no specific meaning and that’s because complexity isn’t just about time. As well as an algorithm having a time complexity it also has a space complexity. For example, if an algorithm takes N inputs and needs to store each of them it has a liner space complexity, where the amount of memory used is directly proportional to the number of inputs. Again, the units are irrelevant, what matters is that we can compare like for like when comparing time and space complexities.

The fact that we measure both time and space complexities is because we care about both when we’re considering how efficient an algorithm is. In general, a bad algorithm will cost a lot of time and space. A reasonable algorithm will only cost us space or time (or a reasonable trade-off of each) and a good algorithm costs little of either. As hinted, this is often referred to as the Space/Time trade-off. Generally speaking you can make things faster by using more space. Put another way, we can often improve how something takes to run at the cost of the amount of memory it uses.

Big O

When comparing time and space complexities we need to use a notation that is both simple and consistent. For this we’re going to use the Big-O notation. This is a very simple notation that represents time and space complexity as a function of O. Using this notation linear time is represented as O(n) and quadratic time as O(n^2).

Amortized time

When calculating the time complexity we’ll be considering its amortized time complexity rather than it’s worse case time complexity. Although the two are mostly the same the latter is more helpful as the worse case isn’t necessarily going to happen or even if it does it’s still not going to be an accurate reflection of the actual complexity.

For example, when pushing back data into a C++ vector we might reach a point where more memory needs to be allocated. Although the C++ Standard doesn’t prescribe the allocation strategy to be used it is often just a simple case of the allocated memory being doubled. Without going into the details, this results in a linear time complexity that involved allocating a memory block twice the size of the existing, copying the existing data from the old to the new block and then freeing the old block. This means that on some occasions the complexity to push back isn’t constant; however, because this reallocation of memory happens only occasionally (and assuming geometric memory reallocation) we can ignore these occasional anomalies and just treat all push backs as constant.

Brute Force

Starting from the number 1, iterate through the array and look to see if the number can be found. If we reach the end of the array we know that is the missing number. If we find the number in the array we start the process again, this time looking for the number 2. We repeat this process, looking for each number in turn, until we are unable to locate the number in the array. At that point we’ve identified the missing number.

How efficient is this?

We start with 1 and we have to search the whole array to see if it’s there. On average, we will have to search at least 50% of the array before we find the number so we can assume our average time complexity for searching just for one number is O(N/2). We fail to find 1 so we now repeat the process for the number 2. We do this until we hit the number that’s missing .

What is the total time complexity? Well, on average we’ll have to search of at least 50% of the numbers before we find the one that is missing. For each number we look for it we need to iterate through, on average, at least 50% of the array. Therefore the time complexity for this is going to be O(n/2) x O(n/2).

We can simplify that to O((n/2)^2) and since we want to know the amortized time we can simplify further to O(n^2). This is called quadratic time and it isn’t really what one could all efficient. Just adding one extra element to the array means we have to search the whole array one more time.

We can do better than this!

Sorting

Sort the array and then iterate through it. Since we know that each and every number from 1 to N must be there as soon as we find a gap we’ve found what would be the missing number. For example, if the current number is 5 and the next is 7 then it is clear the missing number is 6.

How efficient is this?

Assume we use a sorting algorithm that gives us O(n log n) time complexity (for example, quick sort) . We then need to iterate through the array, which is O(n) so our total time is O(n log n) + O(n). Since we want amortized time we can simplify that further to be just O(n log n). Put another way, we have to first of all wait for the array to be sorted and then we can start looking for the missing number.

We can do better than this!

Bit field

Create a bit field, where we have one bit for each element in the original array. Iterate the original array and for each number we find set the corresponding bit in the bit field. For example,  if we find number 4 we set the 4th bit in the bit field. Once we’re finished iterating the array we’ll have a bit field where all but one bit is set. The bit that is not set corresponds to the missing number.

How efficient is this?

We’re iterating the array and we only need to do this once. That has a time complexity of O(n). For each iteration of the array we need to set a bit, which has a constant time complexity O(1). We can simply that to O(n x 1) and further to O(n). In other words, we now have a constant time algorithm. W00t! But, hold on. Efficiency isn’t just about performance. We now have linear time complexity but we also have linear space complexity.

In other words, the size of the space we require to execute this algorithm is directly proportional to the size of the data we’re processing. If we have a 500 element array we need 500 bits. But, what if this is a large amount of data? What if the size of the array was huge. Do we really want an algorithm where the memory requirements scale up in direct proportion to the data we’re processing?

We can do better than this!

Triangles

The solution lays with triangles, or more specifically triangular numbers. You see, if we picture all the numbers from 1 through 9 as a number of dots representing that number we can imagine them laid out such that they look like a triangle.

1:         *
2:        * *
3:       * * *
4:      * * * *
5:     * * * * *
6:    * * * * * *
7:   * * * * * * *
8:  * * * * * * * *
9: * * * * * * * * *

Right, so far so good but how does this help us solve our original problem? Well, if you look you’ll see that the result is actually an equilateral triangle. Each side has the same number of dots. It just so happens that there is a nice simple mathematical formula we can use to calculate how many does there would be given the number of dots on one side.

T(n) = n(n + 1) / 2

If we plumb the numbers into this formula we get this.

T(9) = 9(9 + 1) /2

T(9) = 9(10) /2

T(9) = 90 /2

T(9) = 45.

So, for an array of 9 elements the sum of all the numbers should be 45. Let’s see if that’s right.

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

Yay! It works. Um… how does that help?

Ok, let’s perform that last sum again, but let’s remove the number 5.

1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 = 40

Notice the relationship between the number removed and the result? Of course, we removed 5 so the result if 5 less, or put another way 45 – 5. That’s right, we can find the missing number simply by calculating how many dots should be in the triangle and then subtracting from it the number of dots that are actually in the triangle. Put another way, we can figure out the sum of all the items that should be in the array and then subtract the sum of the items that are actually in the array. the result is the number we are looking for.

Let’s write some code. As always, I’m going to use Python for this as it’s a nice simple language, which will allow us to focus on the problem and not the syntax of the language. I’ve annotated the code with liberal comments so it should be pretty easy to follow.

#-------------------------------------------------------------------------------
# Name:        missing
# Purpose:     find the missing number in an array
#
# Author:      ricky
#
# Created:     01/12/2012
# Copyright:   (c) ricky 2012
# Licence:     MIT
#-------------------------------------------------------------------------------

# T(n) = n(n + 1) / 2
def t(n):
    return n * (n+1) / 2

# This array has the number 5 missing
a = [1,2,3,4,6,7,8,9]

# Size of the array plus one to account for the fact that one that is missing
n = len(a) + 1

# Calculate the triangle number for n
x = t(n)

# Get the sum of the items actually in the array
s = sum(a)

# The difference between T(n) and sum(a) is the missing number
r = x - s

# Display the result
print 'The missing number is {0}'.format(r)

How efficient is this?

The solution has to iterate through the array to sum up all the values, which is linear O(n) time complexity. Calculating the triangle number takes constant amortized time O(1). The memory requirements are also O(1) because no matter how big the array we never need more than a handful of variables to store the result of the math. In fact, using variables is just a convenience, we don’t actually need to use any really.

So, is this efficient? It’s about as efficient as it’s going to get. I am not aware of a way of doing this in less that O(n) time and as far as I know there is no better way of doing this. If you know better please do post a comment and let me know your secret sauce.

Conclusion

We’ve see here that there is often more than one way to do something but we’re also seen that not all algorithms are equal. On face value the problem posed is trivial and yet when looking at the various ways of implementing a solution we’ve seen that the most trivial way to solve it is probably not the way to go. In fact, the best solution turns out to require a little bit of lateral thinking and some simple algebra.

Not all simple problems have simple solutions and my advice would be that Google is your friend. There is rarely a programming problem you’ll face that hasn’t already been solved before. Google for this question and you’ll find plenty of solutions. Some good and some poor. Generally speaking, the one I’ve demonstrated here is the most popular.

Encore

For a bit of fun I decided to take the things discussed in this article and write a small program that does a little magic. Actually, it doesn’t do any magic but I just thought it would be fun to do something semi-practical with the final solution.

#-------------------------------------------------------------------------------
# Name:        card trick
# Purpose:     magic card trick using python
#
# Author:      ricky
#
# Created:     01/12/2012
# Copyright:   (c) ricky 2012
# Licence:     MIT
#-------------------------------------------------------------------------------

# for shuffling
import random

# all the cards in a full deck ([A]ce, [H]earts, [D]iamonds, [S]pades, [C]lubs)
cards = [
    'AH', '2H', '3H', '4H', '5H', '6H', '7H', '8H', '9H', 'JH', 'QH', 'KH',
    'AD', '2D', '3D', '4D', '5D', '6D', '7D', '8D', '9D', 'JD', 'QD', 'KD',
    'AS', '2S', '3S', '4S', '5S', '6S', '7S', '8S', '9S', 'JS', 'QS', 'KS',
    'AC', '2C', '3C', '4C', '5C', '6C', '7C', '8C', '9C', 'JC', 'QC', 'KC',
    ]

# names of rank and suit
names = {
    'A':'Ace', 'H':'Hearts', 'D':'Diamonds', 'S':'Spades', 'C':'Clubs',
    '1':'one', '2':'two', '3':'three', '4':'four', '5':'five',
    '6':'six', '7':'seven', '8':'eight', '9':'nine',
    'J':'Jack', 'Q':'Queen', 'K':'King'
    }

# create a deck of cards
deck = range(1, 52)

# and now let's make some magic...
print 'choose a card, any card'
card = random.choice(deck) - 1
rank = names[cards[card][0]]
suit = names[cards[card][1]]

print 'Show the audience... but not me'
print '* the audiences sees you have chosen the {0} of {1} *'.format(rank, suit)

print 'Mark your card and put it back in the deck'
deck[card] = 0

print 'Finally, shuffle the desk'
random.shuffle(deck)

print 'I will now try and guess your card'
siz = len(deck)
exp = siz * ((siz + 1) /2)
val = sum (deck)
xcard = (exp - val) - 1
xrank = names[cards[xcard][0]]
xsuit = names[cards[xcard][1]]

print 'Was your card the {0} of {1}?'.format(xrank, xsuit)
print '* the audiance goes wild! ... applause ... cheer! *'