N-Repeated Element in Size 2N Array

Problem

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique elements.
• Exactly one element of nums is repeated n times.

Return the element that is repeated n times.

Constraints

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 104
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

Solution

The problem N-Repeated Element in Size 2N Array can be solved by finding an element that appears twice. Based on the problem description, out of 2 * n elements, n + 1 of them are unique. Since a single element is repeated n times, it is guaranteed that the rest of the n elements are all unique. Therefore, the element that appears twice is the only element that can be repeated n times.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int repeatedNTimes(vector<int> &nums)
    {
        bitset<10001> hashset;
        for (int num : nums)
        {
            if (hashset.test(num))
                return num;
            hashset.set(num);
        }

        return -1;
    }
};