Facebook Interview Question
SDE1sCountry: United States
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.
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.
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 :)
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)
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 :)
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.
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.
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++) {
set.add(i);
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);
// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}
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
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]) {
missing.add(temp);
temp = temp+1;
}
} else {
findMissingSortedArrNoRepetitions(arr, start, (start+end)/2, missing);
findMissingSortedArrNoRepetitions(arr, (start+end)/2, end, missing);
}
}
}
}
In Java:
public static Set<Integer> findMissingNumbers(int arr[], int m) {
Set<Integer> set = new HashSet<Integer>();
// dealing with array that does not start with 1
for (int i = 1; i < arr[0]; i++) {
set.add(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[0] + 1) - arr.length))
- (arr[0] - 1);
// dealing with the any extra tail's numbers
for (int i = 1; i <= m; i++) {
set.add(arr[arr.length - 1] + 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++) {
set.add(i);
}
return;
}
int middle = (start + finish) / 2;
// right
findMissingNumbersBetweenToIndexes(arr, set, start, middle);
// left
findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
}
Although, I would just do this for the last loop:
for (int i = arr[arr.length - 1] + 1; i < arr.length + m; i ++) {
set.add(i);
}
Without calculating how much is still missing
for now let us assume that the code
for (int i = arr[start] + 1; i < arr[finish]; i++) {
set.add(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.
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
{
result.Add(missingNum);
}
while ((missingNum+=step) != arr[right]);
}
return result;
}
int middle = (left + right) / 2;
result.AddRange(FindMissing(arr, left, middle));
result.AddRange(FindMissing(arr, middle, right));
return result;
}
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.
Code in c:
#define SIZE(x) sizeof(x)/sizeof(x[0])
int result[100] = {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;
}
Python 3
def answer(n, m, arr):
return set(range(1, n + 1)).difference(set(arr))
# or...
def answer(n, m, arr):
if m == 0:
return {}
current, cnt = 1, 0
s = set()
for x in arr:
if not current == x:
s.add(current)
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])) # {}
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);
}
}
This solution only recurses into one half of the array. There may be missing numbers in both halves at the same time, though.
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));
Try this out...
function returnMissingDetails(int []a, start, end)
{
int temp = a[0] ;
for(int i=0; i<(start - end) ; i++)
{
if (a[i] != temp)
{
CWL("Missing number is {0}", (temp)) ;
i--;
}
temp ++;
}
}
//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) {
missingList.add(array[lo]+1);
if(missingList.size() == missingElements) return;
}
if(array[mid+1] - array[mid]!=1) {
missingList.add(array[mid]+1);
if(missingList.size() == missingElements) return;
}
if(array[mid] - array[mid-1]!=1) {
missingList.add(array[mid-1]+1);
if(missingList.size() == missingElements) return;
}
if(array[hi] - array[hi-1]!=1) {
missingList.add(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);
}
def driver(arr, n, m):
if len(arr) == 0:
return set(range(1, n + 1))
s = set()
for i in range(1, arr[0]):
s.add(i)
bst(arr, 0, n - m - 1, 0, s)
for i in range(arr[n - m - 1] + 1, n + 1):
s.add(i)
return s
def bst(arr, left, right, miss, s):
if right - left <= 1:
for i in range(arr[left] + 1, arr[right]):
s.add(i)
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.
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);
}
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;
}
}
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[0];
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);
set.add(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;
}
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)
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);
}
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[1] + start - 1 + amc) && (Arr[end] == Arr[1] + end - 1 + amc))
return;
else
{
if (start == end)
{
if(Arr[start]!=Arr[1]+start-1+amc)
{
for(int i=start+amc;i<Arr[start];i++)
{
missing.Add(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++)
p.missing.Add(i);
}
foreach (int i in p.missing)
Console.WriteLine(i);
Console.ReadLine();
}
}
}
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;
}
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++)
{
result.Add(i);
}
}
else
{
int pivot = (end+start)/2;
result.AddRange(CoreFindMissingNumbers(pivot, end);
result.AddRange(CoreFindMissingNumber(start, pivot + 1);
}
return result;
}
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.
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
values.add(arr[mid]+1);
}
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
values.add(arr[low]+1);
}
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("}");
}
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++) {
[array addObject:@(i)];
}
}
}
return array;
}
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++) {
[array addObject:@(i)];
}
}
}
return array;
}
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) {
result.add(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));
}
}
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);
}
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.
- Matoy December 05, 2014