## Facebook Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
2
of 4 vote

We divide the array into 2 equals parts and foreach subarray - we check if the number of elements that are actually in there (meaning the highest value minus the lowest value) matches the number of element of that sub array. If so (meaning the difference is zero) the function weill return from this subarray and do nothing. otherwise, we check if we got array that is actually a pair arr[i],arr[i+1] that has a difference bigger than 1. if so we add all the numbers from arr[i] to arr[i+1].
the complexity is m*log(n). I'm assuming that m is a constant value because if he isn't (say m==n/2) that it will take n/2 times to insert m elements into the set (and O(n/2)>O(log(n))) - so I don't see how to implement it without the assumption m is not a const.

``````public static Set<Integer> findMissingNumbers(int arr[], int m) {

Set<Integer> set = new HashSet<Integer>();
findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length - 1, m);
return set;
}

public static void findMissingNumbersBetweenToIndexes(int[] arr,
Set<Integer> set, int start, int finish, int m) {
if (m == 0) {
return;
}
if (start + 1 == finish) {
for (int i = arr[start] + 1; i < arr[finish]; i++) {
m--;
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle,
(arr[middle] - arr[start] + 1) - (middle - start));

// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish,
(arr[finish] - arr[middle] + 1) - (finish - middle));
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I liked your idea to check whether there are missing numbers in each half (by subtracting one end from another and comparing to the number of elements). Clever and simple.

Comment hidden because of low score. Click to expand.
0

I also thought about this approach, but have problem. You have a pair. How can you be certain to get to the other pair? For instance:

1 3 5 7

Let's say you visit pair 1 3 and detect 2. How can you be certain you will also visit 3 5 and detect 4. Once you split, you cannot get element from the other half.

Also, you are missing the situation of missing at the beginning and the end. for instance, starting with 5. need to detect 1, 2, 3, 4. And also, ending with N-5. You need to detect N-4 and etc.

Comment hidden because of low score. Click to expand.
0

Ah, I see you are having middle in both sides, not bad. But what about edges?

Comment hidden because of low score. Click to expand.
1
of 1 vote

I thought you start with 1, and end with n - but if not, you can easily add 1 to the first position in the array and n the the last place of the array and gives m=m-2
shouldn't add time to the complexity :)

Comment hidden because of low score. Click to expand.
0

well maybe adding to the array is not the right term :)
just make two while loops for the start and for the finish (in case we don't start with 1 or end with n)

Comment hidden because of low score. Click to expand.
0

But very clever to include middle in both half so we can look at every pair of interest, I thought about pair solution but could not come up with this trick. And if no missing, discard the entire chunk so deepening only where missing. You could have also not pass m but detect that nothing is missing instead of m==0, would make it even simpler :)

Comment hidden because of low score. Click to expand.
0

This is good lesson for me because I got stock thinking edges have to be handled on every recursion. If you just take care of them once, the whole problem becomes easier. I had another solution that was not working because of that, where I could place missing into array instead of Set. It also was passing missing as param, only missing from-to indexes, so you could know exactly where to place each missing item. May be will post it later.

Comment hidden because of low score. Click to expand.
0

I will up-vote if you handle edges. Because this way it will be a lesson to everyone that sometimes edges should be handled once instead of recursively.

Comment hidden because of low score. Click to expand.
0

can't edit but I reposted the code with the correct modification.

Comment hidden because of low score. Click to expand.
0

What happens if the input array is {5} ?

Comment hidden because of low score. Click to expand.
0

right... so lets make it:

``````public static void findMissingNumbersBetweenToIndexes(int[] arr,
Set<Integer> set, int start, int finish) {
if (arr.length == 1) {
return;
}
if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
return;
}
if (start + 1 == finish) {
for (int i = arr[start] + 1; i < arr[finish]; i++) {
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);

// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think that's the mistake. The mistake is here:

``if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {``

You should not have + 1 there

Comment hidden because of low score. Click to expand.
0

I do not think this catches the situation where 1 is missing, but the question says 1...n so I guess it is ok. otherwise you would need an specific case for when one is not there.

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````void findMissingSortedArrNoRepetitions(int arr[], int start, int end, List<Integer> missing) {
if(start < end) {
if(arr[end] - arr[start] == end - start) {
return ;
} else {
if(end - start == 1) {
int temp = arr[start] + 1;
while(temp != arr[end]) {
temp = temp+1;
}
} else {
findMissingSortedArrNoRepetitions(arr, start, (start+end)/2, missing);
findMissingSortedArrNoRepetitions(arr, (start+end)/2, end, missing);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

In Java:

``````public static Set<Integer> findMissingNumbers(int arr[], int m) {

Set<Integer> set = new HashSet<Integer>();
for (int i = 1; i < arr; i++) {
}
// dealing with the middle elements
findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length - 1);
// recalculate m for any extra tail's numbers
m = m - (((arr[arr.length - 1] - arr + 1) - arr.length))
- (arr - 1);
// dealing with the any extra tail's numbers
for (int i = 1; i <= m; i++) {
}

return set;
}

public static void findMissingNumbersBetweenToIndexes(int[] arr,
Set<Integer> set, int start, int finish) {
if (arr.length == 1) {
return;
}
if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
return;
}
if (start + 1 == finish) {
for (int i = arr[start] + 1; i < arr[finish]; i++) {
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);

// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}``````

Comment hidden because of low score. Click to expand.
0

Although, I would just do this for the last loop:

``````for (int i =  arr[arr.length - 1] + 1; i < arr.length + m; i ++) {
}``````

Without calculating how much is still missing

Comment hidden because of low score. Click to expand.
0

I know, just added it to try to make it more readable to others...

Comment hidden because of low score. Click to expand.
0

for now let us assume that the code

``````for (int i = arr[start] + 1; i < arr[finish]; i++) {
}``````

in the function "findMissingNumbersBetweenToIndexes" is O(1) (i.e m << n). Then the complexity of your function would be
T(n) = 2T(n/2) + O(1)
upon calculating, you'll get T(n) = O(n)
For O(logn), you should have T(n) = T(n/2) + O(1)
Correct me if I am wrong.

Comment hidden because of low score. Click to expand.
0

lets take the worths case where there are m elements and each one of the m number is seprated between two numbers
i.e (1,3,5,7) and not (1,6).
then we will do binary search (O(log(n)) for each missing number (m) which will give us: m*log(n) which in case m is constat will give O(log(n))

Comment hidden because of low score. Click to expand.
1
of 5 vote

``````public static List<int> FindMissing(int[] arr, int left, int right)
{
List<int> result = new List<int>();
if ((right - left) == 1)
{
if (Math.Abs(arr[right] - arr[left]) > 1)
{

int step =  Math.Sign(arr[right] - arr[left]);//left>right returns -1  left<right returns 1
int missingNum = arr[left] + step;
do
{

}
while ((missingNum+=step) != arr[right]);
}

return result;
}

int middle = (left + right) / 2;
return result;
}``````

Comment hidden because of low score. Click to expand.
0

Cleanest so far

Comment hidden because of low score. Click to expand.
0

Although, just please handle not starting from 1 and not ending with N

Comment hidden because of low score. Click to expand.
0

This is not O(log). You are blindly dividing an array until you get to the difference one ... thus checking every possible i,j (where i-j =1) ... Asymptotically it is O(n)

I think interviewer is looking for O(m*log n) answer i.e. for every missing number it should be log(n) operations.

Comment hidden because of low score. Click to expand.
0

Code in c:

``````#define SIZE(x) sizeof(x)/sizeof(x)
int result = {0};
int result_size;

void find_missing(int a[], int start, int end)
{
if (start >= end)
return;
if (end-start == 1) {
if ((a[end] - a[start]) > 1) {
int step = a[end] - a[start];
int missingNum = a[start] + 1;
result[result_size++] = missingNum;
}
return;
}
int mid = (start + end)/2;
find_missing(a, start, mid);
find_missing(a, mid, end);
}

int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 8};
find_missing(a, 0, SIZE(a)-1);
while(result_size)
printf("%d\n", result[--result_size]);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Python 3

``````def answer(n, m, arr):
return set(range(1, n + 1)).difference(set(arr))

# or...

if m == 0:
return {}
current, cnt = 1, 0
s = set()
for x in arr:
if not current == x:
if cnt == m:
return s
current = x
cnt += 1
current += 1
return s

print(answer(8, 2, [1, 2, 4, 5, 6, 8]))  # {3, 7}
print(answer(2, 0, [1, 2]))              # {}``````

Comment hidden because of low score. Click to expand.
0

Your solution is O(nlogn) and isn't correct if there are consecutive missing number. For instance:

[1, 3, 5, 6, 8, 9]

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Solution

``````public static void bsearch( int[] num, int start, int end)
{
int mid  = (start+end)/2;
if(start == end )
return;
if( (mid+1) < num.length && num[mid]+1 < num[mid+1])
{
System.out.println(num[mid]+1);
}
else if( (mid) > 0 && num[mid-1]+1 < num[mid])
{
System.out.println(num[mid]-1);
}
else if(num[mid] == mid+1)
{
// right
bsearch(num, mid+1, end);
}
else
{
//left
bsearch(num, start, mid-1);
}
}``````

Comment hidden because of low score. Click to expand.
0

This solution only recurses into one half of the array. There may be missing numbers in both halves at the same time, though.

Comment hidden because of low score. Click to expand.
0

I ran this and this will find only one missing number

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is m log (n-m) solution. Provided that m is within constant (find very few missing numbers out of very many), this would be close to log n solution.

The idea is divide and conquer. Think about missing numbers as making indexes of array delay from value. If delay is the same within entire partition, there are no missing here and we are not computing this region. We are deepening only in partitions where there is missing, and for one missing this would be log (n-m).

``````static Set<Integer> findMissing(int[] input, int N) {
Set<Integer> result = new HashSet<Integer>(N-input.length);
findMissing(input,result,0,input.length-1, 0, N+1);
return result;
}

static void findMissing(
int[] input, Set<Integer> result,
int start, int end,
int valBefore, int valAfter) {

int delayAtBegin = input[start] - start;
int delayAtEnd = input[end] - end;

if ( delayAtBegin == delayAtEnd ) {
for (int i = valBefore+1; i < input[start]; i ++) result.add(i);
for (int i = input[end]+1; i < valAfter; i ++) result.add(i);
return;
}

int endM = (start+end)/2;
int startM = endM+1;

findMissing(input,result,start,endM,valBefore,input[startM]);
findMissing(input,result,startM,end,input[endM],valAfter);
}``````

Test with:

``System.out.println(findMissing(new int[]{1,2,4,5,6,8},8));``

Comment hidden because of low score. Click to expand.
0

You can't achieve O(log n) anyway, since constructing a result of size m must take at least O(m) anyway.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Try this out...

``````function returnMissingDetails(int []a, start, end)
{
int temp = a ;
for(int i=0; i<(start - end) ; i++)
{
if (a[i] != temp)
{
CWL("Missing number is {0}", (temp)) ;
i--;
}
temp  ++;
}
}``````

Comment hidden because of low score. Click to expand.
0

It works, but it's not O(logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Another Java solution. Function takes the # of missing elements as the parameter
private static	void findMissingElements(int [] array, int lo, int hi,int missingElements,List<Integer> missingList) {
//boundary condition
if(missingList.size() == missingElements) return;
if(lo>=hi) return;
int mid = lo +(hi-lo)/2;
//search for neighborhood of lo,hi and mid and see if there are missing elements
if(array[lo+1] - array[lo]!=1) {
if(missingList.size() == missingElements) return;
}
if(array[mid+1] - array[mid]!=1) {
if(missingList.size() == missingElements) return;
}
if(array[mid] - array[mid-1]!=1) {
if(missingList.size() == missingElements) return;
}
if(array[hi] - array[hi-1]!=1) {
if(missingList.size() == missingElements) return;
}
//search both in halves
findMissingElements(array,lo,mid,missingElements,missingList);
findMissingElements(array,mid+1,hi,missingElements,missingList);

}
public static void main(String[] args) {
//arr = [1,2,4,5,6,8]
int [] array = new int [] {1,2,4,5,6,8};
List<Integer> missingList = new ArrayList<Integer>();
findMissingElements(array, 0,array.length-1, 2, missingList);
System.out.println(missingList);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def driver(arr, n, m):
if len(arr) == 0:
return set(range(1, n + 1))
s = set()
for i in range(1, arr):
bst(arr, 0, n - m - 1, 0, s)
for i in range(arr[n - m - 1] + 1, n + 1):
return s

def bst(arr, left, right, miss, s):
if right - left <= 1:
for i in range(arr[left] + 1, arr[right]):
return
mid = (left + right) / 2
diff = arr[mid] - mid - 1
if diff > miss:
bst(arr, left, mid, miss, s)
miss = diff
bst(arr, mid, right, miss, s)

n = 8
arr = [1, 2, 4, 5, 6, 8]
m = n - len(arr)
s = driver(arr, n, m)
print s #set([3, 7])``````

Driver prints out the numbers between 1 and the smallest number in list, process the list, and prints out the numbers between the largest number in list and n.
In function bst, variable "miss" stands for number of founded missing numbers on the left of arr[mid], variable "diff" means the number of missing numbers on the left of arr[mid].
Therefore, if diff > miss, it means there are some missing numbers we didn't found on the left of arr[mid], thus we need to search the left part of the list. Otherwise, we can proceed to the right part.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in C++. It's O(logn) by performing binary search. It always controls how many missing numbers there are in each half in order to avoid unnecessary searches.

``````void missingNumbers(const IntVector &V, int s, int e, int m, int offset, IntVector *missing)
{
if (m == 0) return;
if (s > e) return;

int mid_idx = (s+e)/2;
int mid_element = V[mid_idx];

int new_offset = mid_element - (mid_idx+1);
int delta_offset = new_offset - offset;

int new_m = m;
int delta_m = 0;
int delta_deltas = delta_offset - delta_m;

if (delta_offset > 0) {
int j = (mid_idx > 0) ? V[mid_idx-1]+1 : 1;

for (; j < mid_element; ++j) {
missing->push_back(j);
--new_m;
}

delta_m = m - new_m;
delta_deltas = delta_offset - delta_m;

if (delta_deltas > 0) {
missingNumbers(V, s, mid_idx-1, delta_deltas, offset, missing);
}
}

missingNumbers(V, mid_idx+1, e, new_m - delta_deltas, new_offset, missing);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MissN{
static int l=0;
public static void main(String [] args){
int [] arr={1,2,4,5,6,8};
int n=8;
int m=2;
findM(arr,0,5);
}
public static void findM(int [] arr,int i,int k){
int x=i+1;
if((arr[x]-arr[i])==1){
if(k!=x){
int j=(i+k)/2;
if(x!=j)
findM(arr,x,j);
findM(arr,j,j+1);
int s=j+1;
if(s!=k)
findM(arr,s,k);
}
else
return;
}
else{
int p=arr[i]+1;
System.out.print(" "+p);
l=l+1;

}
if(l==2)
return;
if(x==k)
return;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``This code is good for only this array. It's not working for other``

Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically I kind of do a binary search. I look at the middle of the array, and calculate the expected value if the array wasn't missing numbers from start to index, and end to index. If the values are what I expected for the left, then I don't check the left half. I do the same for the right. If it isn''t the expected value, I check the adjacent numbers to see if there is a gap and print out those numbers.

``````public static void main(String [ ] args)
{
Set<Integer> set = new HashSet<Integer>();
printMissingNumbers(8, 8, new int[] {1,3,5,9,10,11,15}, set);
Set<Integer> set2 = new HashSet<Integer>();
printMissingNumbers(8, 1, new int[] {1,2,3,4,5,6,7,8,9,11}, set2);
}
static public void printMissingNumbers(int n, int m, int[] arr,
Set<Integer> set) {
int start = arr;
int end = arr[arr.length - 1];
printMissingUtil(start, end, m, arr, set);
}
static public void printMissing(int startNum, int endNum,
Set<Integer> set) {
for(int i = startNum + 1; i < endNum; i++) {
System.out.println(i);
}
}
static int num = 0;
static public int printMissingUtil(int start, int end,
int m, int[] arr , Set<Integer> set)
{
num++;
System.out.println("iteration: " + num);
int index = arr.length/2;
int expectedLeft = index + start;
int expectedRight = end - (arr.length - (index + 1));
int currentVal = arr[index];

if(expectedLeft < currentVal) {
if(currentVal - arr[index - 1] != 1) {
printMissing(arr[index - 1], currentVal, set);
m -= (currentVal - arr[index - 1] - 1);
}
if (m == 0) {
return 0;
}
int newend = arr[index - 1];
m = printMissingUtil(start, newend, m,
Arrays.copyOfRange(arr, 0,index ), set);
}
if(expectedRight > currentVal) {
if(arr[index + 1] - currentVal != 1) {
printMissing(currentVal, arr[index + 1] ,set);
m -= (arr[index + 1] - currentVal - 1);
}
if(m == 0)
return 0;
int newstart = arr[index + 1];
m = printMissingUtil(newstart, end, m,
Arrays.copyOfRange(arr, index + 1, arr.length  ), set);
}
return m;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find(a, left, right, result):
if left == right:
return

if left == right - 1:
if a[left] < a[right] - 1:
for i in range(a[left] + 1, a[right]):
result.append(i)
else:
mid = (left + right) / 2

if a[mid] - a[left] > mid - left:
find(a, left, mid, result)

if a[right] - a[mid] > right - mid:
find(a, mid, right, result)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Before this method, take care of appending to a if first element is lesser / last element is greater

``````static Run findMissing(int a[], int start, int end) {
// only one element
if (start == end) {
return new Run(a[start], a[end]);
}

// this subarray is already sorted
if (a[start] == start && a[end] == end) {
return new Run(a[start], a[end]);
}

int mid = start + (end - start) / 2;

Run leftSide = findMissing(a, start, mid);
Run rightSide = findMissing(a, mid + 1, end);

// FInd missing numbers from leftSide.right -> mid
for (int i = leftSide.right + 1; i<a[mid]; i++) {
System.out.print(i + " ");
}

// Find missing numbers from mid+1 -> rightSide.left
for (int i=a[mid]+1; i<rightSide.left; i++) {
System.out.print(i + " ");
}

return new Run(leftSide.left, rightSide.right);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````using System;
using System.Collections.Generic;

namespace TestRun
{
class Program
{
int[] Arr = new int[] {0,1,4,5,6,8 };
List<int> missing = new List<int>();
int amc = 0;

public void FindMissing(int start, int end)
{

if ((Arr[start] == Arr + start - 1 + amc) && (Arr[end] == Arr + end - 1 + amc))
return;
else
{
if (start == end)
{
if(Arr[start]!=Arr+start-1+amc)
{
for(int i=start+amc;i<Arr[start];i++)
{
amc++;
}
return;
}
}

int mid = (start + end) / 2;
FindMissing(start, mid);
FindMissing(mid + 1, end);
}

}

//Main Program to Call the Function
static void Main(string[] args)
{
Program p = new Program();

int totalElement = 8;
int endIndex = p.Arr.Length - 1;

p.FindMissing(1,endIndex);

if(p.Arr[endIndex]!=totalElement)
{
for (int i = p.Arr[endIndex] + 1; i <=totalElement; i++)
}

foreach (int i in p.missing)
Console.WriteLine(i);

}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````set<int> getMissing(int* input, int low, int high, int missing)
{
static set<int> result;
static int calls = 0;
calls++;

if (low > high || low < 0 || high < 0 || result.size() == missing)
return result;

if (low + 1 == high || low == high )
{
int temp = input[low] + 1;
while (temp < input[high])
{
result.insert(temp);
temp++;
}
//check lower boundary
if (low > 0)
{
int temp1 = input[low - 1];
while (temp1 + 1  < input[low])
{
result.insert(temp1 + 1);
temp1++;
}
}

//check upper boundary
int temp2 = input[high];
while (temp2 + 1 < input[high+1])
{
result.insert(temp2 + 1);
temp2++;
}
}

unsigned int  mid = (low + high) / 2;

//both half sets missing a number
if (input[mid] != mid && mid >= 2)
{
getMissing(input, low, mid-1, missing);
getMissing(input, mid+1, high, missing);
}

return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````List<int> FindMissingNumbers(int[] array, int missing)
{
return CoreFindMissingNumbers(array, 0, array.Length);
}

List<int> CoreFindMissingNumbers(int start, int end)
{
List<int> result = new List<int>();

if(end-start) == (A[end] - A[start]); // Do nothing as there is no missing numbers here
else if(end-start == 2)
{
for(int i = A[start] + 1; i < A[end]; i++)
{
}
}
else
{
int pivot = (end+start)/2;

}

return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code:

``````#include <vector>
using namespace std;

void findmissing(vector<int> data, int start, int end, vector<int> &result)
{
int expected = start + result.size() + 1;
if (start == end)
{
if (data[start] != expected)
{
result.push_back(expected);
}
return;
}
if (data[start] == expected && end - start == data[end] - data[start])
{
return;
}
int mid = start + (end - start) / 2;
findmissing(data, start, mid, result);
findmissing(data, mid + 1, end, result);
}``````

Explanation:

In the base case, we have a single integer. If that integer does not match what is expected at that index (accounting for missing integers already in the result set), we know that we are missing the number that *is* expected at that index.

In the next case, we can ignore this entire set of numbers if we know the first number is correct, and the difference between the first number and the last number is the same as the difference between the first index and the last index. If the initial data set is complete, this will keep us from ever having to iterate over the data.

Finally, we split the data in half, and recurse on each half. Note: It's very important that we recurse on the left half first, as the two cases above depend on all missing numbers to the left of our current starting index to already exist in the result set.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````I don't know why u require m in all of the above solution.

my solution is: -

public static void findMissingNumber(Set<Integer> values,int[] arr,int low, int high){

if(low>=high||arr==null) {
return;
}
int mid = (low+high)/2;
if(mid<high&& (arr[high]-arr[mid])!=high-mid){
if(high==mid+1){
//there is a missing number here
}
else{
findMissingNumber(values,arr,mid,high);
}
}
if(low<mid&&(arr[mid]-arr[low])!=mid-low){
if(mid==low+1){
//there is a missing number here
}
else{
findMissingNumber(values,arr,low,mid);
}
}

}

public static void main(String[] args) {
int[] arr = {1,2,4,5,6,8};
Set<Integer> sets = new HashSet<Integer>();
findMissingNumber(sets, arr, 0, arr.length-1);
System.out.print("{");
for(Integer i:sets){
System.out.print(i+",");
}
System.out.println("}");

//second set of integers
//int[] arr1 = {8,10,12,15};
int[] arr1 = {1,3,5,7};
sets.clear();
findMissingNumber(sets, arr1, 0, arr1.length-1);
System.out.print("{");
for(Integer i:sets){
System.out.print(i+",");
}
System.out.println("}");

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

What about a solution like this : just iterate once over array and grab two neightbors, if difference between them is greater than 1, than we can iterate over their difference and find missing numbers

O(n)
NSArray *missingNumbers(NSArray *a){
if(a.count < 2){
return [NSArray new];
}

NSMutableArray *array = [NSMutableArray new];
for (NSInteger i = 0; i < a.count - 1; i ++) {
NSNumber *x = a[i];
NSNumber *y = a[i+1];

NSInteger xInt = [x integerValue];
NSInteger yInt = [y integerValue];

NSInteger diff = yInt - xInt;

if(diff > 1){
for (NSInteger i = xInt + 1; i < yInt; i++) {
}
}
}
return array;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

NSArray *missingNumbers(NSArray *a){
if(a.count < 2){
return [NSArray new];
}

NSMutableArray *array = [NSMutableArray new];
for (NSInteger i = 0; i < a.count - 1; i ++) {
NSNumber *x = a[i];
NSNumber *y = a[i+1];

NSInteger xInt = [x integerValue];
NSInteger yInt = [y integerValue];

NSInteger diff = yInt - xInt;

if(diff > 1){
for (NSInteger i = xInt + 1; i < yInt; i++) {
}
}
}
return array;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like binary search. If some part of array doesn't contain skipped element it wouldn't process that part.

``````import java.util.*;
public class Middle {
public static void middle(int[] data, int b, int e, int bI, int eI, List<Integer> result) {
if(bI < eI) {
int mid = (bI + eI) / 2;
if(data[mid] - b > mid - bI) {
middle(data, b, data[mid], bI, mid, result);
}
if(e - data[mid] > eI - mid) {
middle(data, data[mid] + 1, e, mid + 1, eI, result);
}
} else if(bI == eI) {
for(int i = b; i <= e; i++) {
if(data[bI] != i) {
}
}
}
}
public static List<Integer> middle(int[] data, int n) {
List<Integer> result = new ArrayList<>();
middle(data, 1, n, 0, data.length - 1, result);
return result;
}

public static void main(String... args) {
int[] data = new int[] {1,2,4,5,6,8};
System.out.println(middle(data, 8));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution using modified binary search.

Running time is roughly O( log N), except for the corner case where missing numbers are on both end of array. (e.g. {2,3,4,5,6,7}). In that case, Running time is O(N).

``````#include<list>
#include<iostream>

using namespace std;

void find_missing(int* input, int s, int e, int m, int n, list<int>& result)
{
if (s>e || result.size() == m)
return;

int half = s + (e-s)/2;
if (half == 0)
{
for (int i = 1; i < input[half]; i++)
result.push_back(i);
result;
}

if (half == n-m-1)
{
for (int i = n; i > input[half]; i--)
result.push_back(i);
return;
}

if (half > s && input[half]-input[half-1] > 1)
{
for (int i = input[half-1]+1; i< input[half]; i++)
result.push_back(i);
}
if (half < e && input[half+1] - input[half] > 1)
{
for (int i = input[half]+1; i<input[half+1]; i++)
result.push_back(i);
}

if (s< half &&  (input[half-1]- input[s] > (half-1)-s || input[half-1]-1 > half-1))
find_missing(input, s, half-1, m,n, result);

if (e> half && (input[e] -input[half+1] > e - (half+1) || n - input[half+1] > (n-m -1) - (half+1)))
find_missing(input, half+1, e, m, n, result);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can this handle the input as blow:

n = 8
m = 2
input = {2,3,4,5,6,7}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.