## The missing number

There is an interesting series of **programming job interview challenges** proposed by Dev102.com, which is now at its tenth puzzle:

This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…

I'm not sure I understood correctly the constraint related to the **memory allocation**.

In my opinion, when they say we are limited to *O(1)*, they mean that we can only allocate a single numeric variable and not any other data structure.

According to this interpretation, the solution is quite easy.

First of all, we take our only variable and store into it the sum of all the numbers between 1 and n + 1, which can be easily computed remembering that *1 + 2 + ... + n = n (n + 1) / 2*.

Then, we subtract each element of the array from this value, eventually the result is actually our missing number.

The functional implementation of this imperative algorithm is straightforward:

#light let sum n = ((n + 1) * (n + 2)) / 2 let answer nums = (nums |> List.length |> sum) - (List.reduce_left (+) nums)

Let's talk about the **complexity of the algorithm**.

If the length of the input list list is known, evaluating the sum of the first *n* natural numbers takes *O(1)*, otherwise we have to scan the entire list, i.e. *O(n)*.

Then we have to subtract each element of the list, and this takes another iteration, so another *O(n)*.

Therefore we have *O(n)* + *O(n)*, which is definitely *O(n)*, and can be easily optimized a little by scanning the list only once.

The only problem left is: "*am I following the instructions*"?

## Google Interview Question: Product of other Elements in an Array in O(n)

Last time I was interviewed for a software development engineer position, the recruiter asked me some of the *classical* **Microsoft interview questions**, such as "*How Would You Move Mount Fuji?*" or "*How many gas station are there in your country?*".

It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.

After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on **algorithms**, **data structures** and **complexity**.

For instance, one of Google interview questions says:

There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

Example:

INPUT:[4, 3, 2, 1, 2]

OUTPUT:[12, 16, 24, 48, 24]Solve it without division operator and in O(n).

Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.

Actually, the product of all elements of *A[]* except *A[i]* is equal to the product of all elements before *A[i]* and those after *A[i]*.

We can traverse *A[]* twice, once from left to right and once in the opposite way and multiply all the elements we find before *A[i]*.

We'll pretend to have a new array called *Output[]* to store the output of the first pass, assigning *Output[i]* the product of all elements preceding *A[i]*:

let rec firstpass product input = match input with | [] -> [] | x::xs -> product :: firstpass (product * x) xs

For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:

let secondpass product input arr = let rev_input = List.rev input let rev_arr = List.rev arr let rec rev_secondpass product (input:list<int>) arr = match arr with | [] -> [] | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)] rev_secondpass product rev_input rev_arr

Both *firstpass* and *secondpass* expect an integer argument called *product*, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.

With these functions we can just define an input array and apply them to get the result.

The following is the complete F# code:

#light let input = [ 4; 3; 2; 1; 2 ] let answer values = let rec firstpass product input = match input with | [] -> [] | x::xs -> product :: firstpass (product * x) xs let secondpass product input arr = let rev_input = List.rev input let rev_arr = List.rev arr let rec rev_secondpass product (input:list<int>) arr = match arr with | [] -> [] | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)] rev_secondpass product rev_input rev_arr values |> firstpass 1 |> secondpass 1 values

## Project Euler in F# – Problem 5

The exercise we are going to face today is ranked as one of the easiest of **Project Euler**'s, so I don't think you will have any problem in solving it.

However, it allows me to discuss a little bit on **algorithm optimization** and how to refine a working solution to obtain a better one.

The text of the exercise says:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Some programming languages (for instance **Haskell**) provide a native function for evaluating the **least common multiple** (LCM) of two numbers, i.e. the smallest positive integer that is multiple of both numbers.

In F# we don't have this function, hence we have to write our own code to perform this calculation, and we need it to be able to find the **LCM of a set of numbers** and not only two.

Let's see the implementation of my algorithm:

#light open System let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1)) let divisibleByList list n = Seq.for_all (fun x -> n % x = 0) list let answer = nums |> Seq.first (fun i -> if divisibleByList [1 .. 20] i then Some (i) else None)

My solution will simply take the integers starting from 1 and check if they are evenly divisible by all numbers from 1 to 20.

We don't know when to stop, so at line 4 we have to create an **infinite list** of integers.

To do so, we use the *unfold* function, which allows us to create a **lazy list** by passing another function to be repeatedly evaluated to provide the elements of the list.

In our case we start from 1 and for each iteration we add one to the previous value, without an upper limit.

At line 6 we have the definition of the *divisibleByList* function, which takes a list of numbers and an integer *n* and checks if *n* is evenly divisible by all the elements of the given list.

This is done by using *Seq.for_all*, which tests if all the elements of the sequence satisfy the given predicate.

We have now everything we need to find our solution.

Let's just feed the *divisibleByList* function with the elements of the infinite list of integers and stop when we find the first that satisfy our conditions, thanks to *Seq.first*.

The solution is complete, but it is not very fast, since it takes about **8 minutes** to run in my computer.

We can improve this time by using some very simple math.

First of all, we are sure that the number we are looking for will be a multiple of 2, so we can **skip all odd numbers**, by changing line 4 with:

let nums = 2 |> Seq.unfold (fun i -> Some (i, i + 2))

With this simple change the execution time drops to **4 minutes**, as the amount of integers to check is is actually halved.

I want to go a little further and instead of checking all even numbers we can just test the **multiples of 20**.

To do so, we change again line 4 with this new one:

let nums = 20 |> Seq.unfold (fun i -> Some (i, i + 20))

Now I can be proud of myself as the execution time is reduced to **25 seconds**, twenty times less than the original solution!

Obviously this is not the only solution and there are smarter approaches, maybe we can see them in a future post.

## Project Euler in F# – Problem 1 (alternative solution)

In the last article I presented a *naive* solution for the first **Project Euler** problem, that asks us to "*find the sum of all the multiples of 3 and 5 below 1000*".

There are many different solutions for the same problem and today I want to show an alternative approach, which is based on a mathematical formula for an arithmetic series.

In our first solution we examined all numbers between 1 and 999 and only kept the multiples of 3 and 5, skipping all the others.

Instead of doing this, we just need to **generate the multiples** of 3 and 5 and sum them, subtracting the multiples of 15 because they will be included twice.

Remembering that the sum of the first *n* integer numbers is equal to *n * (n+1) / 2*, we need to adapt this formula to sum the multiples of a given number, i.e. 3, 5 and 15.

Let's call *n* the the result of the integer division between the maximum value (in our case 999) and *step*, where *step* is 3, 5 or 15.

According to this naming, the sum of multiples will be *step * n * (n + 1) / 2*, and this formula is very easy to translate in **F#**:

#light let sum_mult max step = let n = max / step step*n*(n + 1)/2 let max = 999 let sum = sum_mult max 3 + sum_mult max 5 - sum_mult max 15 print_any sum

At line 2 we define the *sum_mult* function, which takes two integer arguments this time: *max* and *step*.

The next line shows how to define a **local identifier** called *n*, whose scope is limited to the *sum_mult* function.

The rest of the code is straightforward, we apply the formula to sum the multiples of 3 and 5 and subtract those of 15.

Comparing the **complexity** of this solution with the previous one we can easily see that we moved from **O(n)**, i.e. going through all the elements of the array, to **O(1)**.

In fact, with this approach the number of evaluations is always fixed to 3, regardless of the maximum number to take into account.

Next time we'll face a new problem, I look forward to receiving your comments.