In an array there is one element which repeats more than n/2 times...find the number in 0(n) time and 0(1) space

View previous topic View next topic Go down

In an array there is one element which repeats more than n/2 times...find the number in 0(n) time and 0(1) space

Post  Admin on Mon Oct 10, 2011 4:40 pm

//returns -1 if not found
int maxRepeatedElement(int arr[], int size)
{
if( size <= 0)
return -1;


int count = 0;
int elem;



for (int i = 0; i < size; ++i)
{
if (count == 0)
{
elem = arr[i];
count = 1;
}
else if (elem == arr[i])
{
++count;
}
else
{
--count;
}
}

count = 0;
for(int i = 0; i < size; ++i)
{
if (arr[i] == elem)
{
++count;
}
}



if (count > size/2)
{
return elem;
}



return -1;
}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum