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
Page 1 of 1
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
//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;
}
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;
}
Similar topics
» Find pairs in an array that sum to y
» Find the n-th largest int in an array
» Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).
» Find a point in an array where sum of left side array members(wrt to that point) and right side(wrt to that point) are equal..in other words equilibrium point.
» print all subsets of an array whose sum equals one number
» Find the n-th largest int in an array
» Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).
» Find a point in an array where sum of left side array members(wrt to that point) and right side(wrt to that point) are equal..in other words equilibrium point.
» print all subsets of an array whose sum equals one number
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|