Domain 1EasyCORE

N-Repeated Element in Size 2N Array

The problem requires finding an element in an array `A` of size `2N` that appears exactly `N` times. The array contains `N+1` unique elements, with one element repeated `N` times. The constraints are: - `4 <= A.length <= 10000` - `0 <= A[i] < 10000` - `A.length` is even

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

961. N-Repeated Element in Size 2N Array

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 74.6%


Problem Breakdown

The problem requires finding an element in an array A of size 2N that appears exactly N times. The array contains N+1 unique elements, with one element repeated N times. The constraints are:

  • 4 <= A.length <= 10000
  • 0 <= A[i] < 10000
  • A.length is even

The input is an integer array A, and the output should be the integer that appears N times.

Intuition

A brute-force approach would involve counting the occurrences of each element using a dictionary or hash table. However, this approach has a time complexity of O(N) and space complexity of O(N), which might not be optimal given the constraints.

The key insight is that since one element appears N times in an array of size 2N, it must appear at least twice within any four consecutive elements. This observation allows us to reduce the problem to checking pairs of elements, significantly improving efficiency.

Approach

  1. Iterate through the array and check each pair of consecutive elements.
  2. If a pair contains the same element, return that element as it is the one repeated N times.
  3. If no such pair is found (which theoretically shouldn’t happen given the problem constraints), iterate through the array again to find the repeated element.

The algorithm leverages the fact that the repeated element must appear at least twice within any four consecutive elements, thus reducing unnecessary checks.

Complexity Analysis

  • Time Complexity: O(N) - We iterate through the array once or twice.
  • Space Complexity: O(1) - No additional data structures are used beyond a few variables.

Solution

def repeatedNTimes(A):
    # Check each pair of consecutive elements
    for i in range(len(A) - 1):
        if A[i] == A[i + 1]:
            return A[i]
    
    # If no pair is found, check the first four elements (this should not be necessary)
    for i in range(4):
        for j in range(i + 1, 4):
            if A[i] == A[j]:
                return A[i]

# Example usage:
print(repeatedNTimes([1,2,3,3]))  # Output: 3
print(repeatedNTimes([2,1,2,5,3,2]))  # Output: 2
print(repeatedNTimes([5,1,5,2,5,3,5,4]))  # Output: 5

Edge Cases Handled

  • The algorithm inherently handles the case where the repeated element appears at least twice within any four consecutive elements.
  • Although theoretically unnecessary due to problem constraints, the second loop checks the first four elements as a safeguard.