CareerCup

No you can't get it done in less than O(n) in given scenario.

is it means that it has more than one duplicates on one character?

I think it can be done in log N * log N if the number of different elements is log N.

Well generally it can be done in O(log(N)) if duplicates reside at the end of array. Otherwise locating them takes O(log(N)) and removal with shifting in the array O(N)

If the data is raw, you have to go over it at least once. O(n).

if the sorted array with duplicates. i.e. 1 2 2 3 4 4 5 6 7 7 7 8 9 etc. is given.
we should atleast be given tat the elemts are ranging from 1 to n, wher all the numbers between 1 and n are present.. then we can do binary search, calculate wat number to expect in the middle, if that number is lesser than wat is expected, then the left half needs correction. based on this we can come up with some method to skip some numbers, which will make it less than O(n).

CodeBoys:
How do you calculate what number to expect in the middle?
Even if you able to do that then your solution might not work for some cases.

Yeah, it looks like you will need to see every element once, so O(n). I suppose if you knew more about the nature of the input, you might be able to do slightly better. For eg. if you know that a duplicated element always occurs 4 times or more, you could "hop", looking only at every other element and be able to tell that an element is duplicated at least 3 times when you encounter it twice consecutively while hopping.

Plus on a multi-core/multi-proc architecture you could divvy up the array and check in parallel (though that's cheating of course since we are still performing O(n) operations, just in lesser time) and do an "edge check" in the end.

yes it is possible..
algorithm goes as follow..
while(i<n){//n is the length of array,i looping varaible
compare a[i+2] and a[i]
if(a[i+2]-a[i]==2) i=i+2;continue;
if(a[i+2]-a[i]==1) i=i+2;delete last one and continue
if(a[i+2]-a[i]==0) i=i+2;delete the last two element and continue
}
so in this we are skipping numbers (approx o(n/2)).....

limitation : will work only for the input where from 1 to n atleast any number should be present at least one times..
like 1 2 2 3 4 5 5 6 6 6 6 6 6 7 8 9 this...
if we skip number like 1 4 5 5 7 8 ..it won't work

I guess the "less than O(n)" trick is applicable when you have a long string of duplicates. In this case, supposing that you are now at the first element of the duplicated series, you conduct a binary search to with finding the last appearance in mind. If you are lucky, you will get a position that is far away from the first element position. Then you erase everything in between, and then jump to the next element, which be the start of a new round.

If the average number of duplicates in a series is more than log_2 n, the above method is more desirable, and yes, it is less than O(n).

I guess the "less than O(n)" trick is applicable when you have a long string of duplicates. In this case, supposing that you are now at the first element of the duplicated series, you conduct a binary search to with finding the last appearance in mind. If you are lucky, you will get a position that is far away from the first element position. Then you erase everything in between, and then jump to the next element, which be the start of a new round.

If the average number of duplicates in a series is more than log_2 n, the above method is more desirable, and yes, it is less than O(n).

I thought it is pretty easy but I might miss something.
Please correct me which part I have missed.

Since the value is sorted array, duplicated element must be adjacent.
With pointers, compare current and previous element. There is one more pointer called 'pWrite'. It just write non-duplicated element chasing the other pointers.
See my simple code (I assumed the array is characters to keep the code simple but we can do number with one more parameter the size of array)

char *pCur,*pPrev, *pWrite;
	pPrev = value; 
	if(pPrev == NULL) return;

	pWrite = pCur = value+1;
	while(*pCur != NULL)
	{
		*pWrite = *pCur;
		if(*pPrev != *pCur) pWrite++;
		pPrev++;pCur++;
	}
	*pWrite = NULL;
	cout << value << endl;

If I missed something correct me

Will converting into a heap help ? It takes O(log N) times.

Will converting into a heap help ? It takes O(log N) times.

I think we can do this by divide and conquer. Divide the numbers into smaller subproblems; The base case is when there are 2 numbers, compare the numbers, if they are equal delete one of them. Now in order to marge two sub-problems A&B, all you need to consider is the last array element in A(largest) and first array element in B(smallest) and compare, and repeat the process. Essentially the algorithm removes duplicates within subproblems first, and then while merging it removes duplicates across sub-problems.

This takes less than O(n).

For a set of numbers of size 8, we will be doing 4+2+1 comparisons and remove all the duplicates.

I don't think this can be done in less than O(n). We need to read the element at least once to decide if it is a duplicate. Reading itself will cost O(n).

I think you might manage O(m-n) where n is the length of all the duplicates. The reason is that you can divide and conquer and get a lot of early terminations early when you see the beginning and end of a substring are equal, and pass that fact up to a parent to use sometimes on a sibling. So if n is a large number, it could knock the runtime down a lot.