Facebook Interview Question
Country: United States
@Kallu: note the array is sorted, and we only need to search an element a[i] from the array such that a[i]-a[i-1] not equal to the common distance "diff".
What Simon did is different: he tries to find an interval [i,j] such that a[j]-a[i] is not equal to "diff*(j-i)".
Simon's solution is elegant. kudos =) I have simplified the logic a bit in JavaScript
{{
function findMissing_binary(array) {
var diff = Math.min(array[2]-array[1], array[1]-array[0]);
var low = 0, high = array.length-1;
while(low < high) {
if(high - low == 1) {
return (array[high]+ array[low]) / 2;
}
var mid = Math.floor((low + high) / 2);
var leftDiff = array[mid]-array[low];
if(leftDiff > diff * (mid-low)) {
high = mid;
} else {
low = mid;
}
}
return -1;
}
}}
The code does not work for AP with negative difference.
Math.min() returns the larger difference.
Eg:
3
9 7 3
Considering that only one value is missing.
Method 1: Find the sum(S) of AP using:
S = (N/2)(First Term + Last Term);
First Term = a;
Last Term = a+(N-1)*(Delta);
where N = Number of terms in AP,
and, Delta is the difference between any two consecutive terms.
Hopefully this should work. Let me know if I missed anything.
Sorry, im slow and I don't see how your solution works, can you type out the real code for a better picture? Thanks.
can be done in Olog(n) time as first and last term are never missing get last-first/n=d, now go for n/2 th term check if it is larger than a+n/2d then missing term is in first half else second half go on
Brilliant idea. Though I do not see anything in the question that suggests that the first and last items are never missing. In this case though, we would not know if the missing term is the first one or the last term.
@swapnil: Your solution isn't complete. You just found the sum of the A.P in O(1) time. But to find the missing term, you must iterate through the entire array and then find the real sum. The difference of the 2 sums would give you your missing term.
However, all this in O(n).
rdx's solution on the other hand is very elegant.
@teli.vaibhav: Yeah, my solution will take at least one iteration and hence O(n)
@rdx: I think you need to check for the middle term too, whether it is missing?
I think log(n) solution is a very good solution. We have to also take care of increasing or decreasing sequences. So, while checking the middle element we cannot use greater than ">" for both case.
@Zero2, actually no need to check ascending or descending order here. We use 'start' and 'end'. If actualValue[mid] == expectedValue[mid], start=mid+1; otherwise, end = mid.
@gokayhuz if the first/last items are missing, the binary search will not get any result, therefore the complexity is still O(logn)
public static int findMissingTermAP(int n, int[] nums){
if (n < 3) {
//error input
return -1;
}
//exactly one term is missing
int delta = findDelta(n, nums);
if (delta == -1) {
//no missing number
return -1;
}
int first = nums[0];
int actSum = 0;
int idealSum = first;
for (int i = 0; i < n; i++) {
actSum += nums[i];
idealSum += first + delta * (i + 1);
}
return idealSum - actSum;
}
Or we can loop from left to right until we find a difference double any other difference.
This is better than using the formula and subtracting "real sum."
But there are better solutions (let's wait for them).
i don't see any better method. i think we always have to process all the input in the worst case.
The map i -> (a+id) is bijective (because it is degree 1 linear map)
So this reduces to the problem of finding the missing element in the sorted array
0 1 2 ... (n-1) <== we only have to discuss this problem hereon
So the method above we're replying to is roughly equal to scanning left to right until we find an element that doesn't match it's index.
But there is a better way, because checking any random index gets us this information:
1) If number _does_ match index, then everything upto that index is "correct", so the problem must be to the right
2) If number does not match index, then something that happened before to the left (or at that point) has an issue
So:
a , a+1d , a+2d , ... , a+(n-1)d and finding missing element looks daunting, but it is reducible (in both ways) to above problem on {0, 1, ..., n-1}
I may be missing something, since the original question is, as usual for careercup standards, was rush typed to save the original poster 30seconds to 1 min. of precious time.
If the question is posted in a rush, we answer in a rush (make our own interpretation and solve our own interpretation of the problem). Fair game I think.
I didn't think too much about it because i was considering reading the input as part of the algorithm complexity.
but you have a point there. the approach you mentioned is much better to actually solve the problem
That seems an interesting point -- if the problem truly is that you "get the input on a single line" that suggests its a string of numbers and spaces. In that case could you avoid having to search the string for all the spaces to split out the numbers? I think that makes it a linear left to right search of O(n) in the obvious way, since you have to do that to even get the input in list form. Any better solution in this case?
If we take it as a list, clearly Urik's solution is best and looks like O(log n).
public static int findMissing(int[] nums, int min, int max,
int difference) {
int middle = (min + max) / 2;
int predicted = middle * difference + nums[0];
while (min < max && max < nums.length) {
if (min == max - 1) {
//the skipped number is between min and max
return (nums[min] + nums[max])/2;
}
else if (nums[middle] > predicted) {
// the skipped number is on the left
return findMissing(nums, min, middle, difference);
} else {
// the skipped number is on the right
return findMissing(nums, middle, max, difference);
}
}
return (nums[min] + nums[max-1])/2;
public static void main (String[] args){
int nums = {3, 5, 7, 9, 11, 15};
int difference = 0;
if (nums[2] - nums[1] == nums[1] - nums[0]) {
difference = nums[1] - nums[0];
} else {
if (nums[2] - nums[1] > nums[1] - nums[0])
System.out.println((nums[2] + nums[1]) / 2);
else
System.out.println((nums[0] + nums[1]) / 2);
return;
}
System.out.println(findMissing(nums, 2, nums.length-1, difference));
}
}
Average of an AP is (first_tearm+last_term)*Number_Of_Elements/2
So expected sum would be (average* number of items).
To get the missing number subtract actual_sum from expected_sum.
Following is the code.
public static int getMissingTermInAP(int[] arr, int n) {
if (n < 3)
throw new RuntimeException("n cannot be less than 3");
int average = (arr[0] + arr[arr.length - 1]) / 2;
int actualSum = 0;
for (int x : arr)
actualSum += x;
return average * n - actualSum;
}
Test Cases:
{-1,3,7,15} => 11
{1,3,7,9} => 5
If we can assume that the first and the last elements are always available, then we can use
return n/2 * (first + last) - Sum_of_Array_Element;
Alternatively, we can do the following:
int FindMissingElement(int *c, int limit)
{
if(c==NULL)
return 0;
int n=sizeof(c)/sizeof(c[0]);
if(n<=limit)
return 0;
for(i=0;i<n-2;i++)
{
if(c[i+1]-c[i]==c[i+2]-c[i+1])
continue;
else
return (c[i+1]+(c[i+1]-c[i]));
}
return 0;
}
A binary search algorithm is able to solve this problem in O(lgn) time complexity.
def missing_item_in_arithmetic_progression(array):
if len(array) < 3:
return None
d = min(array[-1] - array[-2], array[1] - array[0])
if array[-1] - array[0] == d * (len(array)-1):
return None
l = 0
r = len(array) - 1
while r - l > 1:
m = (l + r) / 2
if (array[r] - array[m]) != (r - m) * d:
l = m
else:
r = m
return (array[l] + array[r]) / 2
print missing_item_in_arithmetic_progression([1, 3, 7, 9, 11, 13])
I have a similar solution to 1 explained
why not do this
a1,.........,an
go to n/2 index if (n/2) even then if a(n/2)+a(1) = a(n/4+1)+a(n/4-2)
if (n/2) odd
if a(n/2)+a(1) = 2*a(n/4)
then left half is correct and right has the missing number
this is using the average concept of the AP where sum of first and last term is 2wice the middle term or equal to sum of middle terms
int findMissing(){
Console c = System.console();
String input = c.readLine("Input the length: "):
int length = 0;
try{
length = Integer.parseInt(input);
if(length < 3){
System.out.println("Error input: length should be no less than 3");
System.exit(0);
}
} catch(Exception e){
System.out.println("Please input an integer.");
System.exit(0);
}
input = c.readLine("Input your sequence: ");
int[] A = parse(input); // the parse function converts the string to an int array.
assert(A.length == length);
if(A[1] - A[0] < A[2] - A[1]){
return A[1] + A[1] - A[0];
}
if(A[1] - A[0] > A[2] - A[1]) {
return A[0] + A[2] - A[1];
}
int start = A[0];
int step = A[1] - A[0];
int left = 0;
int right = length - 1;
while(left < right - 7){
int mid = (left+right)/2;
if(A[mid] > start + mid*step){
right = mid-1;
} else {
left = mid + 1;
}
}
for(int i = left; i<right; i++){
if(A[i+1] - A[i] != step)
return A[i] + step;
}
return A[length-1] + step;
}
int findMissing(){
Console c = System.console();
String input = c.readLine("Input the length: "):
int length = 0;
try{
length = Integer.parseInt(input);
if(length < 3){
System.out.println("Error input: length should be no less than 3");
System.exit(0);
}
} catch(Exception e){
System.out.println("Please input an integer.");
System.exit(0);
}
input = c.readLine("Input your sequence: ");
int[] A = parse(input); // the parse function converts the string to an int array.
assert(A.length == length);
if(A[1] - A[0] < A[2] - A[1]){
return A[1] + A[1] - A[0];
}
if(A[1] - A[0] > A[2] - A[1]) {
return A[0] + A[2] - A[1];
}
int start = A[0];
int step = A[1] - A[0];
int left = 0;
int right = length - 1;
while(left < right - 7){
int mid = (left+right)/2;
if(A[mid] > start + mid*step){
right = mid-1;
} else {
left = mid + 1;
}
}
for(int i = left; i<right; i++){
if(A[i+1] - A[i] != step)
return A[i] + step;
}
return A[length-1] + step;
}
public class MissingFinder {
public static int findMissing(int[] list) {
int length = list.length;
long sum = (length + 1) * (list[0] + list[length - 1]) / 2;
for(int i = 0; i < length; i++) {
sum -= list[i];
}
return (int)sum;
}
public static void main(String[] args) {
int[] list = {1, 3, 7, 9, 11, 13};
System.out.println(findMissing(list));
}
}
Little different approach but this one works :
package com.snehal.gainsight.test;
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int N = Integer.parseInt(line);
int arr[];
arr = new int[N];
String line2 = br.readLine();
StringTokenizer st = new StringTokenizer(line2, " ");
int i = 0;
// System.out.println("---- Split by space ------");
while (st.hasMoreElements()) {
arr[i] = Integer.parseInt((String) st.nextElement());
// System.out.println(arr[i]);
i++;
}
int diff1 = arr[1] - arr[0];
// System.out.println("Diff 1 = " + diff1);
int diff2 = 0;
int oddPosition = 0;
int diff2count = 0;
int diff[] = new int[N - 1];
for (int k = 0; k < N - 1; k++) {
diff[k] = arr[k + 1] - arr[k];
}
int count = 0;
for (int p = 1; p < N - 1; p++) {
if (diff[0] != diff[p]) {
oddPosition = p;
count++;
}
}
if (count == 1) {
System.out.println(arr[oddPosition] + diff[0]);
} else if (count > 1) {
System.out.println(arr[0] + diff[1]);
}
}
}
Little different approach but this one works :
package com.snehal.gainsight.test;
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int N = Integer.parseInt(line);
int arr[];
arr = new int[N];
String line2 = br.readLine();
StringTokenizer st = new StringTokenizer(line2, " ");
int i = 0;
// System.out.println("---- Split by space ------");
while (st.hasMoreElements()) {
arr[i] = Integer.parseInt((String) st.nextElement());
// System.out.println(arr[i]);
i++;
}
int diff1 = arr[1] - arr[0];
// System.out.println("Diff 1 = " + diff1);
int diff2 = 0;
int oddPosition = 0;
int diff2count = 0;
int diff[] = new int[N - 1];
for (int k = 0; k < N - 1; k++) {
diff[k] = arr[k + 1] - arr[k];
}
int count = 0;
for (int p = 1; p < N - 1; p++) {
if (diff[0] != diff[p]) {
oddPosition = p;
count++;
}
}
if (count == 1) {
System.out.println(arr[oddPosition] + diff[0]);
} else if (count > 1) {
System.out.println(arr[0] + diff[1]);
}
}
}
I believe that none of the suggestions above considered the case of decreasing AP (i.e. for the input {9,5,3,1} the result should be still 7). The following code does, in O(lgn) complexity:
int len = input.length;
int step = (input[0] + input[len - 1]) / (len + 1);
if (input[0] > input[len - 1])
step *= -1;
int low = 0;
int high = len - 1;
int lastGood = input[0];
while (low <= high) {
int p = (low + high) / 2;
int exp = input[0] + step * p;
if (exp == input[p]) {
lastGood = input[p];
low = p + 1;
}
else {
high = p - 1;
}
}
System.out.println(lastGood + step);
public class fxc {
public static void main(String args[]) throws Exception
{
String br;
int j1=0,k=0,e = 0,a,l = 0;
Scanner s = new Scanner(System.in),s1=new Scanner(System.in);
System.out.println("enter the no of terms : ");
int n=s.nextInt();
int[] arr=new int[50];
int[] d=new int[50];
System.out.println("enter the sequence : ");
br=s1.nextLine();
String[] strarr = br.split(" ");
for(int i=0;i<n;i++)
{
arr[i]=Integer.parseInt(strarr[i]);
}
for(int j=0;j<=n-2;j++)
{
d[j]=arr[j+1]-arr[j];
//System.out.println(d[j]);
}
for(int j=0;j<n-2;j++)
{
if(d[j]<=d[j+1])
{
e=d[j];
l=j;
}
else
e=d[j+1];
l=j+1;
}
a=arr[0];
System.out.println(a+((l+1)*e));
}
}
<?php
function scanLine()
{
$line = trim(fgets(STDIN));
return $line;
}
function scanList()
{
$line = trim(fgets(STDIN));
return explode(" ", $line);
}
function arithmeticProgression($n,$s)
{
$j = 0;
for($i = 0; $i<$n-1; $i++)
{
$diff = $s[$j+1] - $s[$j];
$costant[] = $diff;
$j++;
}
foreach($costant as $c) $elem[$c]++;
foreach($elem as $k=>$v){
if($v>=intval(count($costant)/2)){
$value = $k;
}
}
$j = 0;
for($i = 0; $i<$n-1; $i++) {
$temp = $s[$i] + $value;
if($s[$j+1]!=$temp) {
return $temp;
}
$j++;
}
}
// Main
echo arithmeticProgression(scanLine(),scanList());
echo "\n";
What if We jump to alternate elements and calculate diff
For ex - 1 3 7 9 11 13
Here we start at 1 and then jump to 7 diff = 6 (indexes 0 and 2)
then to 11 diff = 4 (indexes 2 and 4)
Jump until we ascertain the 2 diff values
So next jump will give 4 again which we have already seen . So the solution lies between 0 and 2 and common diff is (4/2 =2)
Now just compute missing vaue
1,3,7 ,start with 1 , next element = 1+2 =3 , matches with array, next element 3+2 = 5 not match 7 so return 5.
Complexity would be less than linear as we would be scanning n/2+3 elements in worst case.
What if We jump to alternate elements and calculate diff
For ex - 1 3 7 9 11 13
Here we start at 1 and then jump to 7 diff = 6 (indexes 0 and 2)
then to 11 diff = 4 (indexes 2 and 4)
Jump until we ascertain the 2 diff values
So next jump will give 4 again which we have already seen . So the solution lies between 0 and 2 and common diff is (4/2 =2)
Now just compute missing vaue
1,3,7 ,start with 1 , next element = 1+2 =3 , matches with array, next element 3+2 = 5 not match 7 so return 5.
Complexity would be less than linear as we would be scanning n/2+3 elements in worst case.
We can use a binary search to optimize this to O(logn)
int findmissingnumber(int A[], int n)
{
int dis1 = A[1] - A[0];
int dis2 = A[2] - A[1];
int dis = dis1<= dis2? dis1:dis2;
return findmissingnumber(A, 0, n-1, dis);
}
int findmissingnumber(int A[], int s, int e, int d)
{
if ((A[e] - A[s]) == d*(e-s))
{
return A[e] + d;
}
if (e - s == 1)
{
return (A[e] + A[s]) / 2;
}
int m = (s+e)/2;
if ((A[m] - A[s]) == d * (m-s))
{
return findmissingnumber(A, m ,e ,d);
}
else
{
return findmissingnumber(A, s ,m ,d);
}
}
#include <stdio.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int a[10],b,c,d,i,j,n;
printf("\n Enter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
b=a[1]-a[0];
c=a[2]-a[1];
d=a[3]-a[2];
if(b==c)
b=c;
else if(c==d)
b=d;
else if(d==b)
b=d;
else
{}
printf("The difference is:%d",b);
for(i=1;i<n;i++)
{
if(a[i]==a[i-1]+b)
{}
else
{
printf("Missing term is:%d",a[i-1]+b);
}
}
return 0;
}
Granted not as elegant or efficient in terms of time complexity, but here is a functional Python implementation executed in O(log n) time:
def missing(inp):
l = len(inp) + 1
step = (inp[0] + inp[-1])/l
for i in range(len(inp)-1):
if inp[i] + step not in inp:
return inp[i] + step
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> a = new ArrayList<Integer>();
Scanner input = new Scanner(System.in);
int noInt = input.nextInt();
input.nextLine();
int i = 0 ;
while(i < noInt){
a.add(input.nextInt());
i++;
}
int a1,a2,a3,cd = 0;
a1=a.get(1)-a.get(0);
a2=a.get(2)-a.get(1);
a3=a.get(3)-a.get(2);
if(a1 == a2 || a1 == a3)
cd = a1;
if(a2 == a3 || a1 == a2)
cd = a2;
int found = 0 ;
for (int j = 0; j < noInt && found != 1; j++) {
if((a.get(j+1)-a.get(j)) != cd){
found = 1;
System.out.print(a.get(j) + cd);
System.out.println(" is d missing no");
}
}
}
public static void getSum(int[] arr) {
int tmp = 0;
HashMap<Integer,int[]> diff = new HashMap<Integer,int[]>();
for(int i =arr.length-1; i >=1; i --) {
int d = arr[i] - arr[i - 1];
int[] values= new int[2];
if(diff.containsKey(d)){
tmp = d;
int[] t = diff.get(d);
values[0] = i;
values[1] = (t[1]+1);
diff.put(d, values);
} else {
values[0] = i;
values[1] = 1;
diff.put(d, values);
}
}
for (Entry<Integer,int[]> entry :diff.entrySet()) {
int[] value1=entry.getValue();
if(value1[1]==1) {
System.out.println("Missing number is = " + (arr[value1[0]]-tmp));
} else {
System.out.println("No element missing");
}
}
}
public static void FindMissingElement(int[] arr) {
int prevDiff = 0;
int currentPos = 0;
prevDiff =arr[arr.length-1] - arr[arr.length-2];
for(int i =arr.length-2; i >=1; i --) {
int d = arr[i] - arr[i - 1];
if(prevDiff != d) {
currentPos = i;
System.out.println(arr[currentPos] + prevDiff - d);
break;
} else {
System.out.println("Perfect Array :)");
}
}
}
public static void FindMissingElement(int[] arr) {
int prevDiff = 0;
int currentPos = 0;
prevDiff =arr[arr.length-1] - arr[arr.length-2];
for(int i =arr.length-2; i >=1; i --) {
int d = arr[i] - arr[i - 1];
if(prevDiff != d) {
currentPos = i;
System.out.println(arr[currentPos] + prevDiff - d);
break;
} else {
System.out.println("Perfect Array :)");
}
}
}
public static void FindMissingElement(int[] arr) {
int prevDiff = 0;
int currentPos = 0;
prevDiff =arr[arr.length-1] - arr[arr.length-2];
for(int i =arr.length-2; i >=1; i --) {
int d = arr[i] - arr[i - 1];
if(prevDiff != d) {
currentPos = i;
System.out.println(arr[currentPos] + prevDiff - d);
break;
} else {
System.out.println("Perfect Array :)");
}
}
}
public static void FindMissingElement(int[] arr) {
int prevDiff = 0;
int currentPos = 0;
prevDiff =arr[arr.length-1] - arr[arr.length-2];
for(int i =arr.length-2; i >=1; i --) {
int d = arr[i] - arr[i - 1];
if(prevDiff != d) {
currentPos = i;
System.out.println(arr[currentPos] + prevDiff - d);
break;
} else {
System.out.println("Perfect Array :)");
}
}
}
public class ArithmeticProgressionSearch {
public int search(int input[]){
int low = 0,high = input.length-1;
int ap = (input[high] - input[low])/input.length;
int middle = -1;
while (low <= high){
middle = (low + high)/2;
if(input[middle] == input[0] + (middle)*ap)
low = middle + 1;
else if(input[middle] > input[0] + (middle)*ap &&
input[middle-1] == input[0] + (middle-1)*ap)
return input[0] + (middle)*ap;
else high = middle - 1;
}
return -1;
}
public static void main(String args[]){
int input[] = {1,7,10,13,16,19,22};
ArithmeticProgressionSearch aps = new ArithmeticProgressionSearch();
System.out.println(aps.search(input));
}
}
Divide and conquer with time complexity O(lgn):
- Simon October 28, 2013/* * binary search. The input must have at least one missing element */ public static int findMissing_binary(int[] array) { assert array != null && array.length > 2; int diff = Math.min(array[2]-array[1], array[1]-array[0]); int low = 0, high = array.length-1; while(low < high) { int mid = (low+high) >>> 1; int leftDiff = array[mid]-array[low]; if(leftDiff > diff * (mid-low)) { if(mid-low == 1) return (array[mid]+array[low]) / 2; high = mid; continue; } int rightDiff = array[high]-array[mid]; if(rightDiff > diff * (high-mid)) { if(high-mid == 1) return (array[high]+array[mid]) / 2; low = mid; continue; } } return -1; }