## Let’s face a Facebook Programming Challenge together: finding the missing term in an arithmetic progression

**Facebook Programming Challenges** are a great way to challenge yourself in a demanding, timed programming task. FPCs usually last between 45-60 min. and ask you to solve a given problem, stated in the description, picking the programming language you feel most comfortable with (i.e. PHP, Java, Python, C, C++, C# and others).

You can write, compile and run your program directly in the editor in the browser, though you’ll probably miss all the features and comfort of your IDE, which you can use anyway if you prefer, as long as you eventually paste, run and test your code in the online editor.

The solution you provide must satisfy a small set of rules, in order for the remote compiler to “understand” your code and must pass a provided set of test cases, otherwise it won’t be considered correct.

# “Why should I try to solve a FPC?”

Well, do you still remember all the times you dreamed of getting the job of your life at a top IT company? Right, **Facebook Programming Challenges** are intended as a means to find top-notch developers from all around the globe. Once you successfully complete a Challenge, you’re highly likely to be contacted by Facebook’s HR department to schedule a phone interview session. If you perform well on both 45-minutes technical tests, well, you’re in!

# A sample Facebook Programming Challenge

Before you dive right into a real **Facebook Programming Challenge**, you should know that Facebook gives you the opportunity to get acquainted with the process by a **sample Challenge**. In the past, they proposed a different Challenge from the one I’ll discuss here, so it is reasonable to think they change them periodically; in order to avoid losing references to our today’s Challenge, I’ll rewrite the description, then I’ll discuss the approach I took to solve it.

# Challenge description

Task:

Find the missing term in an Arithmetic Progression. An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one term from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing term.Input Format:

The first line contains an Integer N, which is the number of terms which will be provided as input. This is followed by N consecutive Integers, with a space between each pair of integers. All of these are on one line, and they are in AP (other than the point where an integer is missing).Output Format:

One Number which is the missing integer from the series.Sample Input:51 3 5 9 11Sample Output:

7Explanation:

You are provided with 5 integers. As you can can observe, they have been picked from a series, in which the starting term is 1 and the common difference is 2. The only aberration, i.e. the missing term (7), occurs between 5 and 9. This is the missing element which you need to find.Constraints:3 <= N <= 2500All integers in the series will lie in the range [-10^6,+10^6].

So, pretty straight, uh? We’re given an arithmetic progression (increasing or decreasing) of arbitrary (positive and/or negative) numbers in the interval [-1 million, +1 million] and we’re asked to find the single missing number in the progression. For example, the missing element in the progression 1, 3, 7, 9 is of course 5. Our program must be capable of giving such a response.

Since there must be a constant difference between consecutive terms (see the problem description above) and since the minimum size for our progressions is 3, we understand easily that this difference can’t be zero, because otherwise we’d have progressions with a single element repeating over and over again (e.g. 3, 3, 3, 3). But in this case we would have no element to find. So, we can legitimately exclude pathological cases of progressions where at least two consecutive numbers are equal, by imposing that couples of any consecutive numbers must contain non-equal values. From this, we can naturally deduce we’ll deal only with monotonic progressions; that’s to say, pure always-increasing or always-decreasing progressions, in which any element is strictly greater than or less than the element following.

## Finding the minimal step (or difference)

As said, we have a constraint on the progression: its size must be at least of 3 and at most of 2500 elements. So, our simplest progression (from now on: **series**, in the most general sense of the term: *a series of values*, not a sum) will contain exactly 3 elements and, since we know that the distance between any two consecutive numbers must be always the same and this can’t trivially be zero, we must find the series’ step (or difference) and verify it’s the same between any two consecutive numbers. This will be our general strategy, yet there are some cases which need special meditation. For now, let’s start thinking of some sample series for N = 3.

1) 11, 21, 41

2) 31, 21, 1

The missing element is obviously 31 for series 1) and 11 for series 2).

How do we find the step? If the series is (monotonically) increasing like the series 1), we take the second element (which we’re sure it’s there, since we have at least 3 elements in any series) and subtract the first element from it. Viceversa, if the series is (monotonically) decreasing as in case 2), we take the first element and subtract the second element from it. At this point, an alarm should be sounding desperately. Look at this series:

3) 1, 21, 31

One can easily see that the step here is obviously 10 and the missing element is 11, yet the approach to find the step we described just above is going to fail miserably: our algorithm will think that the step is 21 – 1 = 20. Ops. How do we deal with this? Simple: we improve our strategy of finding the step by not just finding the step we claim to be the real step, but instead finding a left step (the difference between the first two elements in the series) and a right step (the difference between the last two elements in the series). The minimum between these two “proto”-steps will be our final minimal step. Why the minimum? Because our goal is somewhat like filling an hole, so we expect to find a bigger hole than others at some point, which can’t be the real step value, because we must fill it and split it in two; moreover, since there’s exactly one missing number, we can be sure that the bigger hole is the only one to be filled, so there’s no need to scan the entire series for even bigger holes. Note that, in the case of arbitrary series of size N, we expect this bigger hole to be inside – rather than on the edge of – the series, so taking the minimum between the left step and the right step would simply mean picking the minimum between two exactly equal values, which will be both the real step value we need. Let’s try this strategy in practice on series 3) and all will be clear:

leftStep = 21 - 1 = 20

rightStep = 31 - 21 = 10

minimumStep = min(leftStep, rightStep) = 10

So, in O(2) = O(1) we have found the minimal step, without scanning the entire series. A similar reasoning applies in the case of descending series. At this point, half of the work is already done.

## Finding the missing number

Now that we’ve found the minimal step, we can scan the series until we find the “big hole”: when we do find it, we make sure that the value on the left of the hole plus the step is equal to the value on the right of the hole minus the step and then conclude that the missing number is equal to the value on the left of the hole (or on the right) plus the step (or minus the step). That’s it.

In the worst case, this stage has a complexity of O(N), N being the size of the series, so the whole algorithm will be an O(1) + O(N) = **O(N)**.

## Source Code

The image below shows a sample output. Click on it to view and download the entire source code from my GitHub page. In the source code I used a slightly different idea of *step*: I’ve meant it not like the *difference* between two consecutive numbers, but like the *elements that would fit between* two consecutive numbers, so that the step between 2 and 10 wouldn’t be 10 – 2 = 8, but 7, because 7 elements would fit between 2 and 10. I’ve been talking about *differences* merely because it is a more manageable idea, but in practice I’ve found more comfortable working the way I’ve mentioned.

I decided not to cover the cases when the elements in the series are all negative or both negative and positive, but all these cases have been thoroughly tested and showed to work perfectly. Also note that the version hosted on GitHub is a more refined one with respect to the one submitted in the Challenge, because the Challenge needed no input by the user and required no other messages printed on the screen except the missing element. I felt I had to improve that code furthermore and I did.

The code differentiates between increasing series and decreasing series. I didn’t manage to unify the two cases into a general case because, as far as I know, combinations intersects in ways that apparently can’t be unified. Should someone manage to do this, I welcome him or her to let me know in the comments.

## Testing

The code passed the sample test case listed in the problem description and the other hidden (who knows why) six, by first clicking on the *Compile and Test* button and then on the *Test against all testcases* button, and the image below proves this:

## What should have you learnt so far?

When dealing with potentially large collections of objects, it is always a good idea to start rebuilding the problem on the smallest collection ever. In our case, it was of size 3. What should happen when we have a series of only 3 numbers? The missing number could be fitting in only 2 positions (between the first and the second elements or between the second and the third elements). How do we find it? First, we need to find the step, because we know it is fixed, so once we’ve found it we can split the big hole in two and add the step value to the element on the left of the edge… and so on, until we build a strong (in the sense that it respects all the constraints and never fails) algorithm that works perfectly on the all the possible minimal structures. As our algorithm gets stronger and stronger, we can think of what happens if we start to consider larger series: new special cases arise? Does our initial algorithm fail onto these? If no, we can explore new cases further, otherwise we think at how could our algorithm respect them. For example: at a certain point, we’ve found that our algorithm wouldn’t have worked properly in finding the step on certain conditions (namely when the missing element was between the first two or the last two elements). We have thought at how to solve this issue and verified than even for bigger series it would have been possible to find the right step. While the structures get bigger and bigger, at a certain point we can think if we can reasonably abstract the dimension to an arbitrary one and move to edge cases: if our algorithm works on structure of dimension 7, most probably it will work on structures of dimension 8, 9 and 10 and so on. Will it be the case to test even for 11 and 12? Probably not. Probably will make much more sense to test the algorithm for structures of dimension 2499 and 2500 (maybe building such structures programmatically…) – which, I confess, I didn’t.

Another great tip I can give is to write down our thoughts on paper and work heavily on it. Only once things start to become clearer we can write down something on the keyboard, but pens and papers must be a programmer’s best friends. Note that in this article I’ve never mentioned words like Java, array, index. That’s because they refer to the implementation, not the design of a problem’s solution, which completely ignores these concepts. Spend 60-70% of the time working on paper and the remaining 40-30% working on the keyboard and you’ll never regret this. My professor was right, I can tell you this.

## Final considerations

So why did I wrote this article, after all? **Facebook Programming Challenges**, like any **other challenges, **are a great way to test your programming skills in relation to the capabilities hirers want you to have. If, at any point, you feel like lost in the sea (or – better – universe!) of concepts, algorithms, data structures, indices, loops and so on, maybe you should pick up some algorithms and data structures and/or programming books, in order to sharpen those skills the software industry needs you to have.

As a bottom line, I personally think that facing these challenges on a regular basis keeps you mind fresh, opened, reactive to problems in general. Of course you don’t need to stay in line with the industry if your dream job is to become a front-end developer (I myself am currently examining this field more in depth) but, even in that case, I would suggest to stay in shape with such exercises. I certainly will.

Hi Nicola,

I came across this Post of yours, it’s really interesting. After reading your post I made up my mind to solve this Puzzle. I sought of took a lengthy way by inserting cases for various scenarios like Ascending/Descending/Positive Numbers/Negative Numbers etc., was able to solve this Puzzle to some extent and later realized that the Code was also not quite clean. Facebook result was (Only 1 Test Case Passed out of 7)

Issue:

Then I decided to try your solution and to my surprise, None of the Test Cases out of 7 Passes, if the Input is {51, 11, 31, 41, 51}.

Actual Output: “The progression is well formed.”

Expected Facebook Output: 21

If i change the Input to {1, 11, 31, 41, 51} then only the First Test Case Passes.

I have gone nuts trying to figure out what am I missing in my code which is making it fail and that too when the same code is working perfectly fine for you, but to no avail.

Query:

In your code, you make use of an int variable increment which has a value 1 when the series is ascending and -1 when the series is Descending, However the Series in the Facebook Puzzle first Descends and then Ascends again ({51, 11, 31, 41, 51}). So, would this approach still work for this kind of series ??

Here is my Complete Code in C#, the only difference is that I am not using the Scanner Class and performing any initial verification mentioned in the main method, Also I am NOT feeding the Array values manually, Instead I am simply feeding the values through the numbers array. You can simply paste in the C# Section of facebook page.

using System;

namespace ArithmeticProgression

{

public class ArithmeticProgression

{

private static int missingNumberFlag = -10000;

private void printAll(int[] array)

{

//Console.WriteLine(“The geometric progression is: “);

for(int i = 0; i < array.Length; i++)

{

//Console.WriteLine(array[i] + " ");

}

//Console.WriteLine("");

}

// Minimum array.Length is 3

private int findMissingNumber(int[] array, bool debug)

{

// * firstStep is the distance between the first two values in the array, minus 'increment',

// that's to say: firstStep = ]array[i], array[i+1][, for each i in [0, array.Length-2]

// * lastStep is the distance between the last two values in the array, minus 'increment';

// * minimumStep is the minimum between firstStep and lastStep.

//

// We need both steps, because it is not said that the step value in the series is given by

// the distance between the first two elements in the array, especially when the missing element

// would be in position array[1] or in aray[array.Length – 2]; in fact, if we have the progression

// 1 _ 5 7 9 11, where the missing element is obviously 3, the algorithm would mistakenly think

// the step in the progression is 3, instead of 1.

// We find both steps values and take the minimum because if, by absurd, the bigger step would

// be the true step in the progression, we wouldn't have found a smaller step, like we did instead,

// so the smaller must be the true step.

int missingNumber = missingNumberFlag;

int increment = array[0] < array[1]? 1 : -1;

int firstStep = Math.Abs(array[1] – array[0] – increment);

int lastStep = Math.Abs(array[array.Length – 1] – array[array.Length – 2] – increment);

int minimumStep = Math.Min(firstStep, lastStep);

bool ascending = array[0] < array[1] ? true : false;

if(debug)

{

/*Console.WriteLine("");

Console.WriteLine("(DEBUG) ASCENDING: " + ascending);

Console.WriteLine("(DEBUG) increment: " + increment);

Console.WriteLine("(DEBUG) firstStep: " + firstStep);

Console.WriteLine("(DEBUG) lastStep: " + lastStep);

Console.WriteLine("(DEBUG) minimumStep: " + minimumStep);

Console.WriteLine("");*/

}

//If it's an ascending order

if(ascending)

{

for(int i = 0; i < array.Length – 1; i++)

{

if(array[i + 1] – array[i] != minimumStep + 1)

{

if(array[i] + minimumStep + 1 == array[i + 1] – minimumStep – 1)

{

missingNumber = array[i] + minimumStep + 1;

}

}

}

}

else

{

for(int i = 0; i < array.Length – 1; i++)

{

if(array[i] – array[i + 1] != minimumStep + 1)

{

if(array[i] – minimumStep – 1 == array[i + 1] + minimumStep + 1)

{

missingNumber = array[i] – minimumStep – 1;

}

}

}

}

return missingNumber;

}

public static void Main(String [] args)

{

ArithmeticProgression progression = new ArithmeticProgression();

int[] numbers = { 51, 11, 31, 41, 51 };

progression.printAll(numbers);

int missingNumber = progression.findMissingNumber(numbers, true);

if(missingNumber == missingNumberFlag)

{

Console.WriteLine("The progression is well formed.");

}

else

{

Console.WriteLine(missingNumber);

}

}

}

}

I would really appreciate if you could provide your invaluable feedback, awaiting your Response.

Thanks

Sim

Dear Sim, I’m sorry if I’m answering to you so late, but unfortunately I have not much time to follow my blog right now..

Anyway, before diving into the code, be sure you understand what the problem is really all about. This FPC asked to find the missing element in an AP, and the problem itself explains what an AP is mathematically meant to be:

«An Arithmetic Progression is defined as one in which there is a CONSTANT DIFFERENCE BETWEEN THE CONSECUTIVE TERMS of a given series of numbers.»

So, {51, 11, 31, 41, 51} is not an AP. The reason why the output is “The progression is well formed” is because the program cannot find the missing element, so missingNumber (which is initially set to missingNumberFlag = -10000 at line 37), is never subsequently modified and the final if (line 142) evaluates to TRUE, even if obviously the progression is not really well formed.

Now, the reason why the code hosted on GitHub does pass only 1 of the test cases when input {1, 11, 31, 41, 51} is because, as I explained in the “Source Code” section:

«Also note that the version hosted on GitHub is a more refined one with respect to the one submitted in the Challenge, because the Challenge needed no input by the user and required no other messages printed on the screen except the missing element. I felt I had to improve that code furthermore and I did.»

That’s to say, Facebook’s compiler needs a raw version of the program, where no output message is printed and no input from user is requested, otherwise it will get confused and make your program pass only 1 test case over the total. Here you can find the version I submitted to Facebook: http://goo.gl/NpAgu3.

Hope this will help, bye!

There is no need to differentiate between ascending and descending. Nor do you need to treat a missing second element as a special case.

Here is my submission in python. The “find_missing” function was extracted to permit simpler unit testing:

#!/usr/bin/env python

def find_missing(line):

seq = [int(i) for i in line.strip().split(‘ ‘)]

step = seq[1] – seq[0]

last = seq[1]

for num in seq[2:]:

diff = num – (last + step)

if diff:

return last + diff

last = num

return last + step

def main():

# raw_input()

print(find_missing(raw_input()))

if __name__ == ‘__main__’:

main()

Hi Dave, you’re perfectly right when you say there’s no need to differentiate the two cases of ascending or descending order, but in my special case I had to, since – as I mentioned in the article – I wasn’t able to find the way to unify the code in the if-else, and that is due to the implementation I chose, based on indices and distances between elements in the progression. If you know how to merge my if-else you’re welcome.. :)

As to the special case of a missing element, I explained the reason as a comment in the source code. What’s your point of view about this?

Here is the gist of it…

In the following ‘seq’ is the supplied sequence of numbers read from stdin (it is not an AP because one element is missing).

We know that len(seq) >= 3. So it is safe to consume the first two elements and start iteration at the third.

Knowing this we consume them outside the loop and calculate the step interval ‘step’ as seq[1] – seq[0].

There is an edge case where the missing number should be the second in the sequence – i.e. between seq[0] and seq[1]. In this case the calculated step will be double the correct step.

We start iterating over the remaining elements – in Python we can use a slice seq[:2] – and initialise ‘last’ to seq[1].

The algorithm we use is to compare each element in ‘seq’ read from stdin with the value expected when adding ‘step’ to the previous element, ‘last’. The most common case (so we treat it first in the loop to minimise unnecessary comparison operations) is that the difference ‘diff’ between the next element ‘num’ and the expected value ‘last’ + ‘step’, is equal to 0.

The only case where this will not be true is where we have just found a hole in the sequence.

First consider the general case where the calculated step is correct – i.e. the missing element is NOT the second element.

Here ‘num’ > ‘last’ + ‘step’. Specifically ‘num’ = ‘last’ + ‘step’ + ‘step’ and therefore ‘diff’ == ‘step’. So the missing value is given by ‘last’ + ‘diff’.

Now consider the edge case where the second element is missing and we incorrectly calculated ‘step’ as double its correct value.

Here ‘num’ < 'last' + 'step'. Specifically 'num' = 'last' + 'step' – 'step/2' and therefore 'diff' == -'step/2'. And as if by magic the missing value is still given by 'last' + 'diff'. That is we stepped past the hole but 'diff' is negative and equal in magnitude to the "correct" step value which is 'step/2'.

Using 'diff' instead of 'step' when calculating the missing element value automagically handles the sign and size of the correction for us. This is why you don't need to "special case" the edge case.

The final case where the missing element is the last element (which I don't believe was actually tested for) is neatly handled by returning 'last' + 'step' after the iteration has been exhausted.

I believe this is the simplest solution using the least operations for any given sequence, but I could be wrong. All viable solutions would have O(n) running time but of them this solution will exit earliest and perform the least unnecessary comparisons by treating the common case 'diff' == 0 first.

My approach to eliminating special cases is most succinctly explained by the code attached. WordPress ate all my whitespace, but if you are familiar with python it should be clear what the correct indentations are.

In this code example I have also included a find_missing_with_generator function which is more efficient for very large sequences.

This was unnecessary for the challenge but illustrates a useful feature of Python – generators.

The first line of the function defines ‘seq’ as a generator (coroutine) which only calculates the next element in the sequence when asked by a call to seq.next(). I’d strongly recommend Python as a language to use for these challenges as it results in very readable yet short-and-to-the-point code which you can turn out quickly. Language features like generators are also much simpler to make use of than their equivalent’s in many other languages.

http://code.stypi.com/dwhitla/Challenges/missing_ap.py