Find Only Repetitive Element from 1 to n-1

Given an array arr[] of size n, filled with numbers from 1 to n-1 in random order. The array has only one repetitive element. Your task is to find the repetitive element.

Note: It is guaranteed that there is a repeating element present in the array.

Examples:

Input: arr[] = [1, 3, 2, 3, 4]
Output: 3 
Explanation: The number 3 is the only repeating element.

Input: arr[] = [1, 5, 1, 2, 3, 4]
Output: 1 
Explanation: The number 1 is the only repeating element.

Input: arr[] = [1, 1] 
Output: 1
Explanation: The array is of size 2 with both elements being 1, making 1 the repeating element.

Constraints:
2 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ n-1 

Approach 01:

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& numbers) {
        map<int, int> frequencyMap;

        for (int& number : numbers) {
            ++frequencyMap[number];
            if (frequencyMap[number] == 2)
                return number;  
        }

        return -1; 
    }
};

from typing import List

class Solution:
    def findDuplicate(self, numbers: List[int]) -> int:
        frequencyMap = {}

        for number in numbers:
            frequencyMap[number] = frequencyMap.get(number, 0) + 1
            if frequencyMap[number] == 2:
                return number

        return -1

Time Complexity:

• Inserting into map:

  Each insertion and lookup in a map takes \( O(\log n) \), where \( n \) is the number of elements processed so far.

• Total Time Complexity:

  \( O(n \log n) \), where \( n \) is the size of the input array.

Space Complexity:

• Map Storage:

  In the worst case, we store up to \( n \) unique keys in the map: \( O(n) \)

• Total Space Complexity:

  \( O(n) \)