Two Repeated Elements Solution

In this page, we will solve the Two Repeated Elements problem using different approaches: hashing, mathematical, and bit manipulation. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, and C++.

Problem Description

You are given an integer n and an integer array arr of size n+2. All elements of the array are in the range from 1 to n. Also, all elements occur once except two numbers which occur twice. Find the two repeating numbers.

Examples

Example 1:

Input: n = 4, arr = [4, 2, 4, 5, 2, 3, 1]
Output: [4, 2]
Explanation: 4 and 2 occur twice.

Example 2:

Input: n = 2, arr = [1, 2, 1, 2]
Output: [1, 2]
Explanation: 1 and 2 occur twice.

Constraints

• 1 <= n <= 10^5
• The array arr has a length of n + 2.

---

Solution for Two Repeated Elements Problem

Intuition and Approach

The problem can be solved using different approaches such as hashing, mathematical properties, and bit manipulation.

• Hashing
• Mathematical
• Bit Manipulation

Approach 1: Hashing

The hashing approach involves using a hash set to keep track of the elements that have been seen so far.

Implementation

Live Editor

function findTwoRepeatedElements() {
  const n = 4;
  const arr = [4, 2, 4,2, 3, 1];

  const findRepeating = (n, arr) => {
    const seen = new Set();
    const result = [];

    for (let i = 0; i < arr.length; i++) {
      if (seen.has(arr[i])) {
        result.push(arr[i]);
        if (result.length === 2) break;
      } else {
        seen.add(arr[i]);
      }
    }

    return result;
  };

 const result = findRepeating(n, arr);
  return (
    <div>
      <p>
        <b>Input:</b> n = {n}, arr = [{arr.join(", ")}]
      </p>
      <p>
        <b>Output:</b> [{result.join(", ")}]
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @manishh12

 function findTwoRepeated(arr) {
   const n = arr.length - 2;
   const seen = new Set();
   const result = [];

   for (let i = 0; i < arr.length; i++) {
     if (seen.has(arr[i])) {
       result.push(arr[i]);
       if (result.length === 2) break;
     } else {
       seen.add(arr[i]);
     }
   }

   return result;
 }

TypeScript

Written by @manishh12

 function findTwoRepeated(arr: number[]): number[] {
   const n = arr.length - 2;
   const seen = new Set<number>();
   const result: number[] = [];

   for (let i = 0; i < arr.length; i++) {
     if (seen.has(arr[i])) {
       result.push(arr[i]);
       if (result.length === 2) break;
     } else {
       seen.add(arr[i]);
     }
   }

   return result;
 }

Python

Written by @manishh12

 def findTwoRepeated(arr):
     seen = set()
     result = []

     for num in arr:
         if num in seen:
             result.append(num)
             if len(result) == 2:
                 break
         else:
             seen.add(num)

     return result

Java

Written by @manishh12

 import java.util.*;

 class Solution {
     public int[] findTwoRepeated(int[] arr) {
         Set<Integer> seen = new HashSet<>();
         int[] result = new int[2];
         int index = 0;

         for (int num : arr) {
             if (seen.contains(num)) {
                 result[index++] = num;
                 if (index == 2) break;
             } else {
                 seen.add(num);
             }
         }

         return result;
     }
 }

C++

Written by @manishh12

 #include <vector>
 #include <unordered_set>

 using namespace std;

 class Solution {
 public:
     vector<int> findTwoRepeated(vector<int>& arr) {
         unordered_set<int> seen;
         vector<int> result;

         for (int num : arr) {
             if (seen.count(num)) {
                 result.push_back(num);
                 if (result.size() == 2) break;
             } else {
                 seen.insert(num);
             }
         }

         return result;
     }
 };

Complexity Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

tip

These are the three approaches to solve the Two Repeated Elements problem. Each approach has its own advantages and trade-offs in terms of time and space complexity. You can choose the one that best fits your requirements.

References

• GeeksforGeeks Problem: GeeksforGeeks Problem
• Solution Link: Two Repeated Elements Solution on GeeksforGeeks
• Authors GeeksforGeeks Profile: Manish Kumar Gupta

---