#include <iostream>
#include <vector>
#include <set>

class HashTable
{
public:
    HashTable(std::vector<int>& firstArray, std::vector<int>& secondArray)
    {
        if(firstArray.size() > secondArray.size())
        {
            swap(firstArray, secondArray);
        }
        mTableSize = firstArray.size();
        arrayWithNumbersForCheck = secondArray;
        for(size_t i = 0; i < mTableSize; ++i)
        {
            mHashTable.emplace_back();
        }

        for(size_t i = 0; i < mTableSize; ++i)
        {
            mHashTable[hashFunction(firstArray[i])].push_back(firstArray[i]);
        }
    }

    size_t numberOfCommonElement()
    {
        if(mTableSize == 0)
        {
            return 0;
        }
        size_t result = 0;
        for(int i : arrayWithNumbersForCheck)
        {
            if(contains(i))
            {
                ++result;
            }
        }
        return result;
    }

private:
    std::vector<std::vector<int>> mHashTable;
    std::vector<int> arrayWithNumbersForCheck;
    size_t mTableSize;

    size_t hashFunction(const int element)
    {
        return ((9999830011 * element + 4798669) % 97643212667) % mTableSize;
    }

    bool contains(const int element)
    {
        size_t indexInTable = hashFunction(element);
        bool tableContainsElement = false;
        if(indexInTable < mTableSize)
        {
            for (int i : mHashTable[indexInTable])
            {
                if (i == element) {
                    tableContainsElement = true;
                    break;
                }
            }
        }
        return tableContainsElement;
    }
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
size_t numberOfCommonElement(std::vector<int>& firstArray, std::vector<int>& secondArray)
{
    size_t result = 0;

    if(firstArray.empty() || secondArray.empty())
    {
        return 0;
    }
    if(firstArray.size() > secondArray.size())
    {
        swap(firstArray, secondArray);
    }

    sort(firstArray.begin(), firstArray.end());

    size_t left;
    size_t right;
    size_t middle;

    //binary search
    for(int i : secondArray)
    {
        left = -1;
        right = firstArray.size();
        while(left + 1 < right)
        {
            middle = (left + right) / 2;
            if(firstArray[middle] == i)
            {
                break;
            }
            if(firstArray[middle] < i)
            {
                left = middle;
            }
            else
            {
                right = middle;
            }
        }
        if(firstArray[middle] == i)
        {
            ++result;
        }
    }
    return result;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void testOne()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    std::set<int> set;
    for(int i = 0; i < 5000000; ++i)
    {
        set.insert(rand() % 6000000);
    }
    for(int i : set)
    {
        firstArray.push_back(i);
        secondArray.push_back(i);
    }
    firstArray.push_back(-2);
    secondArray.push_back(-1);
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test one" : "Incorrect answer in test one") << std::endl;
}
void testTwo()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    for(int i = 0; i < 100000; ++i)
    {
        firstArray.push_back(i * 2 + (rand() % 10000));
        secondArray.push_back(i * 2 + (rand() % 10000));
    }
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test two" : "Incorrect answer in test two") << std::endl;
}

void testThree()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    for(int i = 0; i < 100000; ++i)
    {
        firstArray.push_back(rand());
    }
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test three" : "Incorrect answer in test three") << std::endl;
}

void testFour()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    firstArray = {2123123123};
    secondArray = {0, 1, 2123123122, 3, 9, 2123123123, 7, 6, 5, 2123123121};
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test four" : "Incorrect answer in test four") << std::endl;
}
void testFive()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    firstArray = {2123123123, -123123123};
    secondArray = {0, 1, 2123123121, 3, 9, 2123123123, 7, -123123122, -123123124, -123123123};
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test five" : "Incorrect answer in test five") << std::endl;
}
void testSix()
{
    std::vector<int> firstArray;
    std::vector<int> secondArray;
    firstArray = {1, 2, 3};
    secondArray = {0, 3, 6, 9, 1, 4, 7, 2, 5, 8};
    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test six" : "Incorrect answer in test six") << std::endl;
}
void testSeven()
{
    std::vector<int> firstArray;
    std::set<int> firstSet;
    std::vector<int> secondArray;
    std::set<int> secondSet;
    size_t firstRandomSize = rand() % 5000000;
    size_t secondRandomSize = rand() % 5000000;
    for(size_t i = 0; i < firstRandomSize; ++i)
    {
        firstSet.insert(rand() % 500000);  //use the set to fill the array with various numbers
    }
    for(int element : firstSet)
    {
        firstArray.push_back(element);
    }
    for(size_t i = 0; i < secondRandomSize; ++i)
    {
        secondSet.insert(rand() % 500000); //use the set to fill the array with various numbers
    }
    for(int element : firstSet)
    {
        secondArray.push_back(element);
    }

    HashTable table(firstArray, secondArray);
    size_t correctAnswer = numberOfCommonElement(firstArray, secondArray);
    std::cout << (table.numberOfCommonElement() == correctAnswer ?
                  "Correct answer in test seven" : "Incorrect answer in test seven") << std::endl;
}

int main()
{
    testOne();
    testTwo();
    testThree();
    testFour();
    testFive();
    testSix();
    testSeven();
    return 0;
}