N-Repeated Element In Size 2N Array Problem


Description

LeetCode Problem 961.

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

1
2
Input: [1,2,3,3]
Output: 3

Example 2:

1
2
Input: [2,1,2,5,3,2]
Output: 2

Example 3:

1
2
Input: [5,1,5,2,5,3,5,4]
Output: 5


Sample C++ Code

This is a C++ solution using a hash table. The time complexity is O(n), and the space complexity is O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int repeatedNTimes(vector<int>& A) {
    int len = A.size();
    int n = len / 2;
    map<int, int> ht;
    for (int i = 0; i < len; i ++) {
        if (ht.find(A[i]) == ht.end())
            ht[A[i]] = 0;
        ht[A[i]] ++;
        if (ht[A[i]] > 1)
            return A[i];
    }
    return ht[A[len-1]];
}

int main() {
    vector<int> A = {1, 2, 3, 3};
    cout << repeatedNTimes(A) << endl;
}




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Vowel Spellchecker Problem

LeetCode 966. Given a wordlist, we want to implement a...

Verifying An Alien Dictionary Problem

LeetCode 953. In an alien language, surprisingly, they also use...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...