Algorithms: How to Find N-Repeated Element in Size 2N Array?

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:
Input: [1,2,3,3]
Output: 3

Example 2:
Input: [2,1,2,5,3,2]
Output: 2

Example 3:
Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:
4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Find N-Repeated Element in Size 2N Array via Set, HashSet

The element must be the only element that is duplicate in the array, therefore we can use set or hashset (or even hash table) to store the numbers that we have known when iterating the array. As long as it appears before in the set, we output the number.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int repeatedNTimes(int[] A) {
        Set<Integer> set = new HashSet<>();
        for (int a: A) {
            if (set.contains(a)) {
                return a;
            }
            set.add(a);   
        }
        throw null; // input array is not what has been described
    }
}

class Solution {
    public int repeatedNTimes(int[] A) {
        Set<Integer> set = new HashSet<>();
        for (int a: A) {
            if (set.contains(a)) {
                return a;
            }
            set.add(a);   
        }
        throw null; // input array is not what has been described
    }
}

O(N) complexity and O(N) space by using a set data structure.

Find N-Repeated Element in Size 2N Array using Random Picks

If we randomly pick two different indices, there is a high chance that the numbers on them will be the same – the majority of the numbers are duplicate (half). We run forever generating two random different indices and compare the values until they are the same – which we have the answer!

1
2
3
4
5
6
7
8

class Solution {
    public int repeatedNTimes(int[] A) {
        Random random = new Random();
        int i, j;
        while ((A[i = random.nextInt(A.length)]) != (A[j = random.nextInt(A.length)]) || i == j  );
        return A[i];
    }
}

class Solution {
    public int repeatedNTimes(int[] A) {
        Random random = new Random();
        int i, j;
        while ((A[i = random.nextInt(A.length)]) != (A[j = random.nextInt(A.length)]) || i == j  );
        return A[i];
    }
}

This algorithm usually runs in constant time – assuming we have a good random number generator. The space complexity is O(1).

Find N-Repeated Element in Size 2N Array based on Pigeon Holes Algorithm

Those N repeative number could be either placed evenly or before/after other N numbers – the pigeon holes principle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int repeatedNTimes(int[] A) {
        for (int i = 0; i < A.length - 1; ++ i) {
            if (A[i] == A[i + 1]) { // any two neighbour numbers 
                return A[i];
            }            
        }
        // could be evenly distributed excluding the above case
        for (int i = 0; i < A.length - 2; ++ i) {
            if (A[i] == A[A.length - 1] || A[i] == A[A.length - 2]) {
                return A[i];
            }
        }
        throw null; // input array is not what has been described
    }
}

class Solution {
    public int repeatedNTimes(int[] A) {
        for (int i = 0; i < A.length - 1; ++ i) {
            if (A[i] == A[i + 1]) { // any two neighbour numbers 
                return A[i];
            }            
        }
        // could be evenly distributed excluding the above case
        for (int i = 0; i < A.length - 2; ++ i) {
            if (A[i] == A[A.length - 1] || A[i] == A[A.length - 2]) {
                return A[i];
            }
        }
        throw null; // input array is not what has been described
    }
}

The above algorithm runs in O(N) time and O(1) constant space complexity.

For C++ and other solutions, please visit GITHUB.

N-Repeated Element in Size 2N Array

• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Pigeonhole Principle)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Random Algorithm)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Math)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Sorting)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Hash Map/Set)
• Algorithms: How to Find N-Repeated Element in Size 2N Array?

–EOF (The Ultimate Computing & Technology Blog) —