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.
In this tutorial we’re going to look at how to calculate the Fibonacci numbers in code. We’ll use two different approaches to this, iterative and recursive, and we’ll examine the pros and cons of both. This tutorial assumes you already know what the Fibonacci numbers are and so I make no attempt to explain the maths behind them.