cpp_src/other/FindMajority.hpp

View this file on GitHub
Last update: 2022-12-31 14:31:38+09:00
Include: #include "cpp_src/other/FindMajority.hpp"

Code

// ABC272G
// need to check if it is actually majority
template <class T>
T find_majority(const V<T>& a) {
    T x = a[0];
    int c = 0;
    for (int i = 0; i < SZ(a); ++i) {
        if (c == 0) {
            x = a[i];
            c = 1;
        } else if (a[i] == x)
            c++;
        else
            c--;
    }
    return x;
}

#line 1 "cpp_src/other/FindMajority.hpp"
// ABC272G
// need to check if it is actually majority
template <class T>
T find_majority(const V<T>& a) {
    T x = a[0];
    int c = 0;
    for (int i = 0; i < SZ(a); ++i) {
        if (c == 0) {
            x = a[i];
            c = 1;
        } else if (a[i] == x)
            c++;
        else
            c--;
    }
    return x;
}