Hi Bittu, Your algorithm uses Linear extra space. which is proportional to the input used.
There is a better algorithm which is linear in time and does alot better . int Majoritycount(int [] A) { int ctr=1; //counter is a variable to indicate the relative importance of the element. as successive matches are encountered increment counter. if a mismatch occurs decrement counter. int candidate = A[0]; //ASSIGN FIRST ELEMENT AS A POTENTIAL CANDIDATE FOR MAJORITY int mindex=0; //holds the index of the maximum element N= a.length( ); for(i = 0 to N){ if(a[i]==a[mindex]) ctr++; //match - incr counter else ctr--; //mismatch - dec counter if(ctr==0) { //this implies that the element at mindex has lost the credibility to become the majority element ctr=1; mindex=i; candidate=A[i]; } return candidate; } } On Sep 10, 7:23 pm, Dave <dave_and_da...@juno.com> wrote: > One problem in your algorithm is that the additional array has to be > large enough to handle all of the values in the array, so, e.g., > multiply all of your values by a million and you will see that the > work goes up by a factor of a million. > > It can be done without the additional array, and therefore in a way > that is independent of the specific values in the array. > Seehttp://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html. > > Dave > > On Sep 10, 7:06 am, bittu <shashank7andr...@gmail.com> wrote: > > > i think my concept is right > > > lets us take array a[1..n];={1,1,1,2,1,3}; > > n=6; > > n/2+1=4; > > > so take another array aux[]; > > > which is very helpful to findout hw much time each elemnt arrive in a > > so its count teh no. of time.. > > > fro i=0 to n > > aux[a[i]]++; > > > so aux now contains aux[]={0,4,1,1,0,0}; > > > and just simply find the maximum which gives the 4 and it is clear 1 > > comes 4 times and which >n/2+1 ans is majority element > > > right me if i m wrong .... > > > Regards > > Shashank "Don't b evil U can Earn while u learn" > > 09166674831 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.