| In an array there is one eleme... | ||||||||||
|
30 Day Risk-Free Guarantee:
100% money back if you're unsatisfied. Book (308 Pages):
 Video (One Hour):
 Resume Review (24 - 48hr)
All Products / Services
|
||||||||||
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
33
Qsort takes O(NlogN). Can you explain your logic.
(Different anonymous) quickSELECT. It's O(n) time but Omega(n) space.
Array space already given as input is used in 2quick select so we can say that no extra space is used so space complexity is constant.
Well, OK, but there's a solution that doesn't modify the input.
taylor.thursday.com/classes/cs307/2/Majority%20Element.pdf
//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;
}
Hi,
This is pretty good. But was wondering is it possible to solve it in the space complexity of O(1) as now its O(2).
-Pallav
You make me cry :))))
O(1) means space which doesn't depend on input size.
And I don't know what is O(2) :))))
abe gadhe gevorgk tera logic nai samajh aaya...
Nice language. What about english ?
@gevorgk
awesome work man!!!!
don't worry what netappreject has said. when such people don't have any point to make this is what they do...
@netappreject
There is better way to say this....Please be nice to people who are sharing their knowledge and helping you...
O(2) is a nonstandard way to say O(1). Pallav, if using two ints bothers you, just pack them both into a long.
@gevorgk - Can you also pls explain, your thinking process - how you approach the problem and devise the solution - I assume here you approached it as the number which occurred more than n/2 has to either alternate starting from 1st position (e.g. 1 2 1 4 1 5 1) or has to occur consecutively atleast 1 (e.g. 5 4 1 1 6 1 1)
If the element is repeated more than n/2 times, than it definitely occurs consecutively atleast once...
I doubt he came up with the algorithm because the code looks very similar to the algorithm in taylor.thursday.com pdf. But if he came up with it great!
This solution has a flaw.
If numbers are in this form
1, 20, 2, 20, 3, 20, 4, 20 ...
Then this solution doesn't work.
Because it never get a chance to store 20 in elem.
if the code is modified a little bit like mentioned below.
......
else
{
--count;
--i;
}
........
Then things work fine.
Ya But then I don't know what will be the complexity.
In worst case It probably comes out to be O(n+n/2), i.e. O(3n/2), i.e. O(n).
Please comment on it.
Please point out if you see any problem in it or type "CORRECT" if it is correct.
- Nitin
Point here is definition of majority is (n/2) + 1. thats way:
1 20 2 20 3 20 4 20 needs to keep another 20, for n/2 it fails several cases.
yes, right.
The solution is correct if 20's are more than n/2.
:-)
Thanks gevorgk.
Hi gevorgk , as you are setting again count=0 . It making count logic of first for loop useless. I am not getting why that is required. also according to my analysis your logic will be definitely failed for array {3,1,1}
The first loop finds the required element if it exists and an arbitrary element otherwise. The second loop checks whether this element occurs more n/2 times, which is sort of pointless given that the input is guaranteed to have that property.
It's not useless, count logic in first loop guarantees that element with more than n/2 occurrence will survive.
And I don't see any problem with {3, 1, 1}.
3 - elem = 3, count = 1
1 - elem = 3, count = 0
1 - elem = 1, count = 1
So we have elem = 1 after first loop and check if it occures more than n/2 in second loop.
nice solution
nice solution gevorgk
/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
1 2 10 42 11
The algorithm, though very clever, does not work in all cases. For example:
1112222111
very gud solution , great work !!
#include<stdio.h>
#define arraysize 6
int array[arraysize]={1,3,3,3,4,3};
int repeatedElem(int array[], int size)
{
int index = 0;
int count = 0;
int val;
int elem;
count = 0;
for(index=0;index<size;++index)
{
elem = array[index];
if(count ==0)
{
val = elem;count++;
}
else if(val == elem)
{
count++;
}
else
{ count--;}
}
if(count>0)
{
return val;
}
else{return -1;}
}
int main()
{
int ans = repeatedElem(array, arraysize);
printf("answer is %d ", ans);
return 0;
}
gevorgk： gorgous solution!
traverse the array from i=0 to n-3
if a[i]==a[i+1] or a[i]==a[i+2]
then num=a[i]
it's simple
I found Bond's solution the best.It works and i'm not that good with calculating complexity but I m sure there is only one for loop so complexity must be less.
find the median element using the quick select algo.