CareerCup

the algo is atleast O(n/2) which is O(n);
take a sample of (n/2)+1 elements . That sample will have the repeated elt ( pigeon hole principle.

1. implement a hashmap ;
2. check whether elt exists in the map ; if so return the elt
3. else insert elt in to hashmap;

Divide array into different grps of size 3. Any grp will have that 2 or more elements common.

One more approach using Mnte Carlo.

Just select any two var at rand, and check if they r equal.
Chance that they are equal is 1/2*1/2 = 1/4 hence not finding prob = 3/4
if same fine
Else
repeat

So on an average you will have to do 4 samplings to find the repeated element.
which is almost constant time, if n >> 4.

Form the Build-Max-Heap from the list of elements , it takes at Max 0(n) time . In the Max-Heapify() algorithm include check for equality , if any element becomes equal then that is the repeating element. The only chance is that all leaf elements becoming equal , just do a manual check once to avoid that case , this can be done 0(2) , so total time 0(n) time.Correct me if i am wrong

time O(N/4)

while(startIdx<endIdx)
{
 if(array[startIdx++] == array[endIdx--]) break;
}

int getDupElem(vector<int> &arr){
if ( arr.size() <= 2 ) return MININT;
for(int i = 0; i < arr.size()-2; i++){
if ( arr[i] == arr[i+1] || arr[i] == arr[i+2] ) return arr[i];
}
return MININT;
}

@anonymous who posted on June 30th 2010, ur solution does not seem to be correct for this case :-

4 , 1 , 2 , 4

n/2 + 2

the question is not clear...how about the array {1, 2}?

Do a quicksort of the array and then return its middle element.

let n be the size of array
therefore p=n/2;

if(a[i]==a[i+1] || a[i]==a[i+2] || a[i]==a[n+i])
return a[i];

I think this will reduce complexity

check the array in blocks of 2 like {0,1} , {2,3} , {4,5} ....
The repeated element can be in each of the different blocks or 2 of them can be in one block .
If two of them are in one block , it can be easily identified in the first round of checking.
If each of the repeated element is in different blocks , then after the first check , none of arr[i] == arr[i+1] will match . In the second round we just check elements in indexes {0,1,2,3} to find out which one is repeated

The above problem can be solved using the concept of the hashmap, where we will first count the frequency of all the integers and then, we will traverse the hashmap and compare check of the frequency if found greater then n / 2 then output the number.