Majority element in an array

[damasta6]

Hi, I'm trying to make a program that finds out the majority element in a user-input. A majority element is an element that is repeated more than half of the number of elements. Let n be the number of elements in a sequence. This would represent a majority element (n/2+1). Lets say a user inputted 11122, the majority element is 1. However if a user inputted 11111223344,then there is no majority element since '1' appears 5/11 times.

So my question is, what method would be the easiest and fastest to approach this problem? I'm thinking of making a counter where it checks every element in a string, and when it comes across a like-element, it increments c++, and when it comes across a different element it decrements c--. So, in the end, if c>=1, "There is a majority element". if c<1, "There is no majority element".

[ne555]

> I'm trying to make a program that finds out the majority element in a user-input
> So, in the end, if c>=1, "There is a majority element". if c<1, "There is no majority element".
¿do you want to know which element is the majority element, or do you want to know if it exists?

Also, ¿is the input sorted?

[damasta6]

You want to know which element is the majority. Also, no, the input is not always sorted. For example, it could look like this:4449484844432154541444

[Daleth]

Why not have 10 counters for each number 0 - 9, increment each one for every matching digit found, then divide each counter by the sum of all the counters? This way, you could check which number accounts for more than 50% of the digits.

[ats15]

If you are comfortable using STL algorithms, you can do the following:
1. create an array with each element
2. sort the array (std::sort)
3. find unique elements (std::unique)
4. in the sorted array find for each of the elements in unique the number of elements (std::equal_range)
You can look in the reference section for <algorithm>. The above procedure will let you find the majority element of an input of ints, chars, or any objects for which you can define the < operator. Like for example, in a list of names, you can find if "John" is a majority element
To improve speed, keep a counter of all the elements which you checked. If more than 50% of the size of the input, then obviously you don't need to check the rest of the unique elements, since they cannot be majority.