N-Repeated Element in Size 2N Array Solutions in C++

// Source : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
// Author : Manu Gond
// Date   : 2019-10-06


 
 class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        map<int,int>myMap;
        for(int i=0;i<A.size();i++){
            myMap[A[i]]++;
        }
        for(auto x:myMap){
            if((x.second)==(A.size()/2)){
                return x.first;
            }
        }
        return 0;
    }
};

/// Source : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
/// Author : liuyubobobo
/// Time   : 2019-08-11

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;


/// Using HashMap to get the frequency
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {

        unordered_map<int, int> freq;
        for(int e: A){
            freq[e] ++;
            if(freq[e] == A.size() / 2) return e;
        }
        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
/// Author : liuyubobobo
/// Time   : 2019-08-11

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>

using namespace std;


/// Using HashSet to check repeating
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {

        unordered_set<int> set;
        for(int e: A)
            if(set.count(e)) return e;
            else set.insert(e);
        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
/// Author : liuyubobobo
/// Time   : 2019-08-11

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>

using namespace std;


/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {

        sort(A.begin(), A.end());
        for(int i = 1; i < A.size(); i ++)
            if(A[i] == A[i - 1])
                return A[i];
        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
/// Author : liuyubobobo
/// Time   : 2019-08-11

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>

using namespace std;


/// Random Algorithm
/// Time Complexity: O(1)
/// Space Complexity: O(1)
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {

        int n = A.size();
        while(true){
            int i = rand() % n, j = rand() % n;
            if(i != j && A[i] == A[j]) return A[i];
        }
        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}