CareerCup

One brute force approach :
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, MARK it as duplicate.
BUT the comparisions are not minimum.:-(

unique consitutes that there is no duplicate in them..so n/2 unique elements have no repeating numbers. Now create a hashmap of all of these n/2 unique numbers with a value of 1 in each corresponding cell.
Now for the rest of n/2 elements, also calculate the hash value and look if the value in hashmap is already one or not. If it is already one, then the element is repeating.
Therefore, the maximum number of comparisons are n/2.
Please correct me if i am wrong.

can we not use hashtable and store number(from array) as key and no of occurrence as value.
from 0-> length on array
try to put number in hastable if already exists then it is duplicate.(1 comparison per number)
store it in some other array if needed.

total n comparision

well we can compare each element[i] with element[i+1],element[i+2] and element[i+3]. The first element[i] satisfying equality with element[i+1] or element[i+2] or element[i+3] will be the answer.
Proof: If its uniform distribution of repeated number, then it will be like unique number1, repeated number, unique number2, repeated number.

It can be something like: unique number1,repeated number,repeated number,unique number2.

Time complexity: o(n) (comparing each i with i+1 and i+2).
Space Complexity: o(1)

I dont understand, half of the elements are distinct and half are unique...what do you mean by distinct...doesn't distinct mean that they are unique....i am totally bowled out here....can anybody explain clearly

Yes, here distinct means they are unique. For eg 2,3,2,4,2,2,7,8

The language of the question is totally confusing. Those who answered, can you please explain by example how do you perceive the array?

@Jumbo, your example array has n/2 unique elements and another element which is repeated n/2 times. Is this the correct representation of the problem?

i think the worst case for minimum is when the array has all unique elements in the beginning e.g: {1 2 3 4 4 4}

the first element has to be compared with n/2 elements..the second one to n/2-1 elements and so on till we have to compare with only 1 element

so total no.of comparions is 1+2+3+....n/2 = (n/2)(n/2+1)/2

Understanding Question:
n/2 Unique Elements means n/2 elements are not Repeated and n/2 distinct elements means n/2 different types of elements. I don't see a case where you will have N/2 unique and N/2 Distinct elements in a array.

Below are my examples:
Ex: [10,2,3,4,4,4]
Unique:3
Distinct:4

Ex: [10,2,3,3,4,4]
Unique:2
Distinct:4

Ex: [10,10,10,10,10,10]
Unique:0
Distinct:1

I cannot come up with a case with N/2 unique and N/2 Distinct elements.Can anyone give an example with N/2 Unique and N/2 Distinct Elements.

ya... wats da difference b/w distinct and unique nos. ?

comparison of each element with its n/2 immediate neighbors would yield the result
however that would be mean at the max (n/2)*(n/2) comparison giving a complexity of n^2

better approach would be to have a hash map of size n/2 and just scanning the array and whenever there is a clash it would yield the result
this would require at the most n/2 comparison (if the repeated element is first repeated at n/2+1 location) and minimum of 1 comparison if the repeating elements are the first two elements of the array
and this approach has an overall complexity of n

example: 234522

assuming n/2 distinct = n/2 number occurring once and n/2 unique = one number occurring n/2 times. in this case
my solution is as following:
compare pair of neighbors .( total n/2 comparison) . if we find any pair to be the same that is our answer.

If we dont find any pair that is to be same ,that means there is only configuration possible and that is the repeated numbers are alternative. in that case: make 2 more comparision: a[0] and a[2] ,a[1] and a[3] , one of these 2 comaprision will be the answer.
so answer = n/2 +2

Use the Majority vote algorithm of O(n)time complexity

Take first 3 elements, compare with one other.. If any repeating element found, that is the answer, else discard these three and get to the next three. Do the same operation.

No of comparisons: 3*n/3 = n, at-most

minimum can be 1 comparison. you get lucky at first trial.
maximum can be n/2 + 1 comparison. You do n/2 comparisons and unfortunately always compare with a unique number. Then take any two pair from these n/2 pairs ans cross compare. If they match, then this is the repeating number. If they do not match, then the other number is the repeating number.

I guess min of n/2 comparisions have to be done . We can as well sort the array in O(nlogn) and 0(1) to find the element tht is repeated n/2 times. By the way sorting the array also involves n/2 comparisions.