Find the missing and repeated element in the given array

In this particular question we are given an array of the size N with the values also in the range 1 to N (both inclusive). Each number in the range 1 to N appears exactly once except for X and Y. The number X appears twice whereas the number Y is missing. The task is to find the repeating and the missing number A and B in the given read only array.

This question can be solved using hashing technique. Using this technique we can store the count of each element between 1 to N. Now the element with the count 2 is the repeating element and the element with the count 0 is the missing element.

Approach

1. Create an hash array of size N+1.
2. Initialize the values of each element in the temp array to 0.
3. Iterate all the elements of the input array and update the values of hash array : 

• hash[a[i]] = hash[a[i]] + 1

4. Iterate the hash array to return the repeating and missing element : 

• If hash[i] == 2, it implies that ‘i’ is the repeating element
• If hash[i] == 0, it implies that ‘i’ is the missing element

Here, hash = hash array, a = given array

Complexity

• Time Complexity: O(N)
• Space Complexity: O(N)

Where N is the size of the given array

Java Code

import java.util.Arrays;

public class FindNumbers {
    public static int[] findMissingRepeatingNumbers(int[] a) {
        int n = a.length; // size of the array
        int[] hash = new int[n + 1]; // hash array


        //update the hash array:
        for (int i = 0; i < n; i++) {
            hash[a[i]]++;
        }


        //Find the repeating and missing number:
        int repeating = -1, missing = -1;
        for (int i = 1; i <= n; i++) {
            if (hash[i] == 2) repeating = i;
            else if (hash[i] == 0) missing = i;


            if (repeating != -1 && missing != -1)
                break;
        }
        int[] ans = {repeating, missing};
        return ans;
    }


    public static void main(String[] args) {
        int[] a = {3, 1, 2, 5, 4, 6, 7, 5};
        int[] ans = findMissingRepeatingNumbers(a);
        System.out.println("Input array is " + Arrays.toString(a));
                          
        System.out.println("The repeating and missing numbers are: {"
                           + ans[0] + ", " + ans[1] + "}");
    }
}

Output

Input array is [3, 1, 2, 5, 4, 6, 7, 5]
The repeating and missing numbers are: {5, 8}