find most occurence element in array

Question

Here is simple program to find the element which occurs most often in an array:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int a[] = {1,2,3,4,4,4,5};
    int n = sizeof(a) / sizeof(int);
    int max = 0;
    int result = 0;
    int *b = new int[n];
    for (int i = 0;  i < n;  i++) {
        b[a[i]] = (b[a[i]] || 0) + 1;
        if (b[a[i]] > max) {
            max = b[a[i]];
            result = a[i];
        }
    }
    cout << result << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

But it doesn't work; it prints 1. Why?

Answer 1

Since you are including vector anway, why not replace int *b=new int [n]; with std::vector<int> b(n)? This also takes care of releasing the memory, you forgot to delete[] b.

But as others have mentioned, your solution will break if the array contains elements larger than n. A better approach might be to count the elements with a mapping to int. That way, you can also count elements that cannot be used as an array index, for example strings.

There is also no reason to limit ourselves to arrays. Here is a generic solution that works with any container of any less-than comparable element type:

#include <algorithm>
#include <iterator>
#include <map>

struct by_second
{
    template <typename Pair>
    bool operator()(const Pair& a, const Pair& b)
    {
        return a.second < b.second;
    }
};


template <typename Fwd>
typename std::map<typename std::iterator_traits<Fwd>::value_type, int>::value_type
most_frequent_element(Fwd begin, Fwd end)
{
    std::map<typename std::iterator_traits<Fwd>::value_type, int> count;

    for (Fwd it = begin; it != end; ++it)
        ++count[*it];

    return *std::max_element(count.begin(), count.end(), by_second());
}

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test {1, 2, 3, 4, 4, 4, 5};
    std::pair<int, int> x = most_frequent_element(test.begin(), test.end());
    std::cout << x.first << " occured " << x.second << " times";
}

Answer 2

You've not initialized your array b. You can do it like this:

int *b=new int [n]();
                  ^^

Once that is done you can increment your frequency array as:

b[a[i]]++;

in place of

b[a[i]]=(b[a[i]]||0)+1;

Your way of doing (b[a[i]]||0)+1 works in languages like Javascript, Perl where an un-initialized array element will have a special value called undef or null. C++ does not have anything like that and an uninitialized array will have garbage.