Facebook Interviewstreet Sample Question

general
, ,
1

I have been trying to work on the sample problem on Facebook’s Interviewstreet page for quite a while. Here is the problem:-

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
5
1 3 5 9 11

Sample Output
7

Explanation
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 abberration, i.e. the missing term (7), occurs between 5 and 9. This is the missing element which you need to find.

Constraints
3 <= N <= 2500
All integers in the series will lie in the range [-10^6,+10^6].


Could someone explain the logic behind the solution to me(c++)? Thanks!
2

hey how about this approach.

 Sum_of_AP = n*(A0 + An)/2
    CalculatedSum = Sum of all the terms
    
    Missing number = Sum_of_AP - CalculatedSum
    
    Time complexity: O(n), Space complexity: O(1)
2 Likes
3

nice and easy problem … there is only one corner case to be handled .

Algorithm:
find the maximum and minimum in given array say a1 is min and aN is max;
and also find the sum of all elements
Now missing number is = Total_sum - N*(a1+aN)/2;
The algorithm is same as @anonymousins

if missing number is zero that means no missing element in that case print the (N+1)th term of AP (this is the corner case).

(N+1)th Term will be (aN + diff)

diff = (aN - a1) / (N-1);

Hope it will help you .

Happy Coding!!!

2 Likes
4

What’s the catch here ? Only if the numbers are scrambled, you should sum them up. Else why not just check if n(i) = n(i-1) + d or not. It is still O(n) but in most of the case you won’t need to look at ints. Better then summing them all up!

5

Time complexity is O(N) and space is constant .

6

Both @upendra1234 and your answers were helpful :slight_smile: