#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

// Given an array arr[]. Find the majority element in the array. If no
// majority element exists, return -1.

// Note: A majority element in an array is an element that appears
// strictly more than arr.size()/2 times in the array.

// Examples: 

// Input: arr[] = [1, 1, 2, 1, 3, 5, 1]
// Output: 1

// Explanation: Since, 1 is present more than 7/2 times, so it is the
// majority element.

class Solution : public testing::Test {
public:
    unordered_map<int, int> majorityMap; // map of key -> count of key

    void clear() { majorityMap.clear(); }
    
    virtual void SetUp() {}
    virtual void TearDown() {}

    vector<tuple<vector<int>, int>> testCases = {
        // array values       majority element
        {  {1,1,2,1,3,5,1},   1 },
        {  {7},               7 },
        {  {2,13},           -1 },
    };    
    
    int majorityElement(vector<int>& arr)
    {
        int majority = arr.size() / 2;
        cout << "majorityThreshold: " << majority << endl;
        cout << "-----------------" << endl;

        for (const auto& i: arr)
        {
            unordered_map<int,int>::iterator iter;
            if (iter = majorityMap.find(i); iter != majorityMap.end())
                iter->second += 1;
            else
            {
                auto result = majorityMap.insert(pair{i, 1});
                iter = result.first;
            }

            // check majority via map duing array traversal, if
            // there is a majority there will only be one
            if (iter->second > majority)
                return iter->first;
        }

        // for (const auto& [key, val]: majorityMap)
        // {
        //     if (val > majority)
        //         return key;
        // }
        
        return -1;
    }

    void print(const vector<int>& v, int majElem)
    {
        cout << "input: ";
        for (const auto& j: v) cout << setw(3) << j << " ";
        cout << endl << "majorityElement: " << majElem << endl;
    }
};

TEST_F(Solution, MajorityElements)
{
    for (auto testCase: testCases)
    {
        clear();        
            
        print(get<0>(testCase), get<1>(testCase));
        
        int majElem = majorityElement(get<0>(testCase));

        EXPECT_EQ(get<1>(testCase), majElem);
    }
}

int main(int argc, char** argv)
{
    testing::InitGoogleTest(&argc, argv);
    
    int ret = RUN_ALL_TESTS();
    
    return ret;
}