Problem

Given an array of n+2 elements. All elements of the array are in range 1 to n and all elements occur once except two numbers which occur twice. Write an algorithm to find the two repeating numbers.

Examples

Example 1:

Input: nums = [1,4,5,6,3,2,5,2]
Output: [2, 5]
Explanation: The number 2 and 5 occur twice, rest of elements occur once.

Similar Problems

Single Number 3 - All elements except two occur twice

Solution

Method 1 - Brute Force

This problem can be solved using two nested loops. For each element, compare it with all other elements, and if it appears twice, add it to list. This approach works even if the numbers are not in the range of 1 to n.

Then this approach is similar to Find duplicates in a given array#Method 1 - Naive

Code

Java
public class Solution {
    public int[] findTwoRepeating(int[] nums) {
        int n = nums.length;
        List<Integer> repeatingElements = new ArrayList<>();

        // Iterate through each element
        for (int i = 0; i < n; i++) {
            // Compare with every other element
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j] && !repeatingElements.contains(nums[i])) {
                    repeatingElements.add(nums[i]);
                }
            }
        }

        // Convert list to array and return
        return repeatingElements.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 2, 4, 5, 2, 3, 1};
        int[] repeating = sol.findTwoRepeating(nums);
        System.out.print("Two repeating elements: ");
        for (int num : repeating) {
            System.out.print(num + " ");
        }
        // Expected output: 4 2
    }
}
Python
def find_two_repeating(nums):
    n = len(nums)
    repeating_elements = []

    # Iterate through each element
    for i in range(n):
        # Compare with every other element
        for j in range(i + 1, n):
            if nums[i] == nums[j] and nums[i] not in repeating_elements:
                repeating_elements.append(nums[i])

    return repeating_elements

# Example usage
nums = [4, 2, 4, 5, 2, 3, 1]
repeating = find_two_repeating(nums)
print("Two repeating elements:", repeating)  # Expected output: [4, 2]

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Sorting

This solution will work even if all the numbers are not in the range of 1 to n. First, sort the array to bring all the repeated elements together. Then traverse the array and compare adjacent elements. If they are the same, add them to the result. This is again similar to Find duplicates in a given array#Method 2 - Sorting.

Code

Java
public class Solution {
    public int[] findTwoRepeating(int[] nums) {
        Arrays.sort(nums);
        int[] repeatingElements = new int[2];
        int index = 0;

        // Traverse the sorted array and find the repeating elements
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                repeatingElements[index++] = nums[i];
                // Stop if found both repeating elements
                if (index == 2) break;
            }
        }

        return repeatingElements;
    }
}
Python
 class Solution:
    def find_two_repeating(self, nums):
        nums.sort()
        repeating_elements = []

        # Traverse the sorted array and find the repeating elements
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                repeating_elements.append(nums[i])
                # Stop if found both repeating elements
                if len(repeating_elements) == 2:
                    break

        return repeating_elements

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 3 - Use HashMap

This solution is effective even if the numbers are not within the range of 1 to n. Maintain a count of each element in a HashMap. Return the elements that have a count of 2.

Code

Java
public class Solution {
    public int[] findTwoRepeating(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int[] repeatingElements = new int[2];
        int index = 0;

        // Count occurrences of each element
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // Find elements with count 2
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == 2) {
                repeatingElements[index++] = entry.getKey();
                // Stop if found both repeating elements
                if (index == 2) break;
            }
        }

        return repeatingElements;
    }
}
Python
from typing import List
from collections import defaultdict

def find_two_repeating(nums: List[int]) -> List[int]:
    count_map = defaultdict(int)
    repeating_elements = []

    # Count occurrences of each element
    for num in nums:
        count_map[num] += 1

    # Find elements with count 2
    for num, count in count_map.items():
        if count == 2:
            repeating_elements.append(num)
            # Stop if found both repeating elements
            if len(repeating_elements) == 2:
                break

    return repeating_elements

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4 - Using Math’s Arithmetic Mean Formula

This solution will work only if all the numbers are in the range of 1 to n and are > 0. Let’s say the two repeated elements are a and b.

  • The sum of 1 to n elements is S.
  • The sum of all array elements is X, so a + b = X - S.
  • The product of 1 to n elements is n!.
  • The product of all array elements is Y, so a * b = Y / n!.

Now we have 2 equations and 2 unknowns. We can solve to get a and b. We know that a - b = sqrt((a + b)^2 - 4ab).

Here is the example:

nums = [1,4,5,6,3,2,5,2], n = 6;

S = n*(n+1)/2 = 6 * 7/2 = 21

X (sum of all array elements) = 28

a + b = 28 – 21 = 7

Product of 1 to 6 = !6 = 720

Y (Product of all array elements) = 7200
a * b = 7200/720 = 10

So now, a + b = 7 and a * b = 10
a - b = sqrt( (a + b)^2 - 4ab )
a – b = sqrt(7*7 – 4*10) = sqrt(49-40) = sqrt(9) = 3
a = (7 + 3)/2 = 5
b = 7-5 = 2

Elements are 5, 2

Code

Java
public class Solution {
    public int[] findTwoRepeating(int[] nums) {
        int n = nums.length - 2;

        // Calculate the sum of 1 to n (S)
        int S = n * (n + 1) / 2;

        // Calculate the product of 1 to n (P)
        int P = factorial(n);

        // Calculate the sum of all array elements (X)
        int X = 0;
        for (int num : nums) {
            X += num;
        }

        // Calculate the product of all array elements (Y)
        int Y = 1;
        for (int num : nums) {
            Y *= num;
        }

        int sum_ab = X - S;
        int product_ab = Y / P;

        int diff_ab = (int) Math.sqrt(sum_ab * sum_ab - 4 * product_ab);

        int a = (sum_ab + diff_ab) / 2;
        int b = (sum_ab - diff_ab) / 2;

        return new int[]{a, b};
    }

    private int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
Python
def find_two_repeating(nums: List[int]) -> List[int]:
    n = len(nums) - 2
    
    # Calculate the sum of 1 to n (S)
    S = n * (n + 1) // 2

    # Calculate the product of 1 to n (P)
    P = math.factorial(n)

    # Calculate the sum of all array elements (X)
    X = sum(nums)

    # Calculate the product of all array elements (Y)
    Y = math.prod(nums)

    sum_ab = X - S
    product_ab = Y // P

    diff_ab = int(math.sqrt(sum_ab * sum_ab - 4 * product_ab))

    a = (sum_ab + diff_ab) // 2
    b = (sum_ab - diff_ab) // 2

    return [a, b]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 5 - Using array index and multiplication (Works for positive elements)

Here is the code : Find duplicates in a ranged array0-n) in O(n) time and O(1) extra space

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 6 - Using XOR

if we know that only 2 elements repeat and that too twice, we can use Single Number 3 - All elements except two occur twice.

XOR all the numbers in the array with all numbers from 1 to n. The result will be X XOR Y. Since 1 XOR 1 = 0 and 1 XOR 0 = 1, the result of X XOR Y where any kth bit is set to 1 implies that either X or Y has a 1 at that position but not both.

We can use this property to divide all the elements in the array and from 1 to n into two groups: one group with elements where the kth bit is set to 1 and the other group with elements where the kth bit is 0.

Identify the rightmost set bit (find more information here). We can then split the elements into two groups and XOR them separately to find X and Y.

Code

Java
public class Solution {
    public int[] findTwoRepeating(int[] nums) {
        int xor = 0;
        int n = nums.length - 2;

        // XOR all numbers from 1 to n and all elements of the array
        for (int num : nums) {
            xor ^= num;
        }
        for (int i = 1; i <= n; i++) {
            xor ^= i;
        }

        // Get the rightmost set bit as the differentiator
        int rightmostSetBit = xor & -xor;

        int x = 0, y = 0;

        // Divide all elements into two groups based on rightmost set bit
        for (int num : nums) {
            if ((num & rightmostSetBit) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        for (int i = 1; i <= n; i++) {
            if ((i & rightmostSetBit) != 0) {
                x ^= i;
            } else {
                y ^= i;
            }
        }

        return new int[]{x, y};
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4, 2, 4, 5, 2, 3, 1};
        int[] repeating = sol.findTwoRepeating(nums);
        System.out.println("Two repeating elements: " + repeating[0] + ", " + repeating[1]);
        // Expected output: 2, 4
    }
}
Python
def find_two_repeating(nums: List[int]) -> List[int]:
    xor = 0
    n = len(nums) - 2

    # XOR all numbers from 1 to n and all elements of the array
    for num in nums:
        xor ^= num
    for i in range(1, n + 1):
        xor ^= i

    # Get the rightmost set bit as the differentiator
    rightmost_set_bit = xor & -xor

    x = 0
    y = 0

    # Divide all elements into two groups based on rightmost set bit
    for num in nums:
        if num & rightmost_set_bit:
            x ^= num
        else:
            y ^= num
    for i in range(1, n + 1):
        if i & rightmost_set_bit:
            x ^= i
        else:
            y ^= i

    return [x, y]

# Example usage
nums = [4, 2, 4, 5, 2, 3, 1]
repeating = find_two_repeating(nums)
print("Two repeating elements:", repeating)  # Expected output: [2, 4]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)