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 repeatedn times.

Examples

Example 1

1
2

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

Example 2

1
2

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

Example 3

1
2

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

Constraints

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

Solution

Method 1 -

Intuition

Since only one element is repeated n times, and all others appear once, we can use a set to find the repeated element efficiently.

Approach

Iterate through the array, add each element to a set. The first element that is already in the set is the repeated one.

Code

1
2
3
4
5
6
7
8

int repeatedNTimes(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return x;
        seen.insert(x);
    }
    return -1;
}
1
2
3
4
5
6
7
8

func repeatedNTimes(nums []int) int {
    seen := make(map[int]bool)
    for _, x := range nums {
        if seen[x] { return x }
        seen[x] = true
    }
    return -1
}
1
2
3
4
5
6
7
8

public int repeatedNTimes(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (seen.contains(x)) return x;
        seen.add(x);
    }
    return -1;
}
1
2
3
4
5
6
7
8

fun repeatedNTimes(nums: IntArray): Int {
    val seen = mutableSetOf<Int>()
    for (x in nums) {
        if (x in seen) return x
        seen.add(x)
    }
    return -1
}
1
2
3
4
5
6
7

def repeatedNTimes(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return -1
1
2
3
4
5
6
7
8

use std::collections::HashSet;
fn repeated_n_times(nums: Vec<i32>) -> i32 {
    let mut seen = HashSet::new();
    for x in nums {
        if !seen.insert(x) { return x; }
    }
    -1
}
1
2
3
4
5
6
7
8

function repeatedNTimes(nums: number[]): number {
    const seen = new Set<number>();
    for (const x of nums) {
        if (seen.has(x)) return x;
        seen.add(x);
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of nums.
  • 🧺 Space complexity: O(n) for the set.