---
###### tags: `Leetcode`
---
# Leetcode 961. N-Repeated Element in Size 2N Array

[link](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/)

---

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.

#### Example 1:

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

#### Example 2:

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

#### Example 3:

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

#### 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.

---

題意: 給一個長度是2n的list: nums, return重複n次的元素

---

Here we can use Hashmap to store each element and when we found the element with a count equal to the length of the list divided by two, it must be the answer.

#### Solution 1

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        d = {}
        for i in range(len(nums)):
            if nums[i] in d:
                d[nums[i]] += 1
            else:
                d[nums[i]] = 1
            
            if d[nums[i]] == (len(nums) // 2):
                return nums[i]

O(T): O(n)
O(S): O(n)

---

But it seems like the code above is too complicated, we can return the element once we found the element with a count larger than one.

#### Solution 2

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        d = {}
        for i in range(len(nums)):
            if nums[i] in d:
                return nums[i]
            else:
                d[nums[i]] = 1
        
        return -1

O(T): O(n)
O(S): O(n)

---

If a number is repeated N times in a list of size 2N, it is always possible for the repeated number to stay within a distance of 2.

Consider the example where N = 6, Number 2 is repeated three times.

[2,X,1,3,4,2]
[2,1,X,3,4,2]
[2,1,3,X,4,2]
[2,1,3,4,X,2]

#### Solution 3

for i in range(len(nums)):
    if nums[i - 1] == num[i] or nums[i - 2] == nums[i]:
        return nums[i]

O(T): O(n)
O(S): O(1)
Reference: Leetcode discussion