Code Logo

N-Repeated Element in Size 2N

Published at23 Jul 2026
Created by
Easy 1 views
Like0

You are given an integer array of size 2N. There are N+1 unique elements in the array, and one of them is repeated exactly N times. All other elements appear exactly once. Find the element that is repeated N times.

A hash set provides the simplest solution: iterate through the array. If an element is already in the set, it is the repeated element (the first duplicate found). This works because the repeated element appears N times, and the first time we encounter it the second time, we know it's the answer.

For example, nums = [1,2,3,3] has N=2. Elements 1 and 2 appear once. Element 3 appears twice (N times). The answer is 3.

This problem tests understanding of hash sets and the ability to recognize that the first duplicate found is guaranteed to be the answer because the N-repeated element appears N times while all others appear exactly once.

The hash set solution works because the N-repeated element appears N times, making it the first element that is encountered a second time. All other elements appear exactly once, so they are added to the set and never seen again. This simple observation makes the problem trivial with a hash set.

The array size is always 2N, with N unique elements plus one element repeated N times. This guarantees that the repeated element will be found before the end of the array.

Example Input & Output

Example 1
Input
[1,2,3,3]
Output
3
Explanation

3 is repeated N=2 times.

Example 2
Input
[5,1,5,2,5,3,5,4]
Output
5
Explanation

5 appears 4 times (N=4).

Example 3
Input
[2,1,2,5,3,2]
Output
2
Explanation

2 appears 3 times (N=3).

Algorithm Flow

Recommendation Algorithm Flow for N-Repeated Element in Size 2N

Solution Approach

Find the element that appears more than n/2 times in an array of size 2n where one element appears n times. Use a hash map to count frequencies. The first element whose count reaches n/2 + 1 is the answer. Alternatively, since the array contains n+1 distinct elements total and one is repeated n times, the repeated element appears at least twice within the first 4 consecutive elements by the pigeonhole principle.

function repeatedNTimes(nums) {
  for (var i = 2; i < nums.length; i++) {
    if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) return nums[i];
  }
  return nums[0];
}

The pigeonhole principle guarantees the repeated element appears within distance 2 in the array. Check each element against its previous two neighbors to find the duplicate.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int n : nums) { if (!seen.add(n)) return n; }
        return -1;
    }
}