961. 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]<=10^4$
• nums contains n + 1 unique elements and one of them is repeated exactly n times.

From: LeetCode
Link: 961. N-Repeated Element in Size 2N Array

Solution:

Ideas:

• The repeated element appears n times, so it must appear more than once early in the scan.

• Create a seen array to track which numbers have appeared.

• Iterate through nums:

  • If a number has been seen before → that’s the repeated one → return it.
  • Otherwise, mark it as seen.

• The problem guarantees a solution, so the first duplicate you find is the correct answer.

Code:

int repeatedNTimes(int* nums, int numsSize) {
    // Since nums[i] is in [0, 10^4], we can use a simple frequency/seen array
    int seen[10001] = {0};  // all initialized to 0

    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        if (seen[x]) {
            // First time we see a repeated element, it must be the answer
            return x;
        }
        seen[x] = 1;
    }

    // Problem guarantees there is always such an element, so we should never get here
    return -1;
}