N-Repeated Element in Size 2N Array

You have an integer array nums of length 2 * n, which consists of n + 1 unique elements. Among these elements, one of them is repeated exactly n times. You are required to find and return that repeated element.

Approach

A straightforward approach to solving this problem is to use a dictionary or hash table to count the occurrences of each element. Since one element is repeated exactly n times, the element with a count of n will be the answer.

Here’s a step-by-step guide:

  1. Create a Dictionary: Initialize an empty dictionary to keep track of the count of each number in the array.

  2. Count the Occurrences: Iterate through the array, and for each number, increment its count in the dictionary.

  3. Find the Repeated Element: Iterate through the dictionary, and return the number that has a count of n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        counts = {} # Step 1: Create a dictionary

        # Step 2: Count the occurrences
        for num in nums:
            if num in counts:
                counts[num] += 1
            else:
                counts[num] = 1

        # Step 3: Find the repeated element
        for num, count in counts.items():
            if count == len(nums) // 2: # Check if count is n
                return num

Key Takeaways

  • We are looking for an element that is repeated exactly n times in an array of length 2 * n.
  • Using a dictionary to count occurrences allows us to easily find the element that meets the given condition.
  • This approach is simple to understand and implement, making use of basic data structures and iteration.