Finding the missing element in an array

sum of consecutive integers from 0 to n-1 , S = n*(n-1)/2;
sum of array , s=calcSum(array)        // O(n) complexity, one loop required

missing number = S-s;

Complexity: O(n)
Space Complexity: O(1)

Instead of using summation formula, it is better to use XOR operator to find the missing element in an array. Because summation can overflow for a very big integer. On the other end, XOR operator will not cause such problem.

// C# program to find missing Number
// using xor

using System;

class Program
{
    // Function to find missing number
    static int getMissingElement (int []a, int n)
    {
        int x1 = a[0]; 
        int x2 = 1; 

        /* For xor of all the elements 
        in array */
        for (int i = 1; i < n; i++)
            x1 = x1 ^ a[i];

        /* For xor of all the elements 
        from 1 to n+1 */   
        for (int i = 2; i <= n + 1; i++) // loop to n+1 because including the missing 
 //number the size of the array will increase by 1
            x2 = x2 ^ i;         

        return (x1 ^ x2); // return final xor result
    }

    public static void Main()
    {
        int []a = {1, 2, 4, 5, 6};
        int miss = getMissingElement(a, 5); // size of array is 5
        Console.Write(miss);
    }

}

def finder(arr1,arr2):
    d={}
    for i in arr1:
        if i in d: 
            d[i]+=1 # if the number is repeated, the value is incremented with 1
        else:
            d[i]=1 # adds all the numbers which are not present in the dictionary
    #print(d)
    for i in arr2:
        if i in d:
            d[i]-=1 # if the number is repeated, the value is decremented with 1
        else:
            d[i]=1 # adds all the numbers which are not present in the dictionary
    #print(d)
    for i in d:
        if d[i]!=0: # The value must not be zero if any number is missing from any of the two arrays, so it will print the missing number(s)
            print(i)
        else:
            return 'No Missing element'



finder(x,y)

/**
     * Time Complexity will be 
     * Arrays.sort(A)  = O (n log n)
     * Binary Search O (log n)
     * 
     * Total Time Complexity = O (n log n) + O (log n)
     * 
     * @param A
     * @return
     */
    private static int getMissingElement(int[] A) {
        Arrays.sort(A);

        int low = 0;
        int high = A.length-1;
        int missingElement = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] != mid+1) {
                high = mid - 1;
                missingElement = mid +1;
            }
            else {
                low = mid + 1;
            }
        }
        if(missingElement == 0){
            return A.length+1;
        }
        return missingElement;
    }

Procedure to approach this question would be:

1. Sort the elements in the array using any sorting algorithm of choice depending on the complexity you want

2. Loop through the sorted Array

3. Check to see if the arr[index + 1] - arr[index] != 1, then It indicates, a number is missing Get the difference between these indexes

4. Create a temporary list to store missing numbers

5. Using a for-loop, from 1 up to the difference range, add 1 to the arr[index] and store in missingNumbers list

6. Now loop through missingNumbers list, to get all your missing numbers

An implementation using Java which caters for both (negative and positive) numbers

import java.util.LinkedList;
import java.util.List;

public class missingElement {

public static void main(String[] args) {

    int values[] =  {17, 1, -4, 2, 3, 4, 6, 7, 9, 8, 10 ,15,23};
    
    int[] arrSorted = sortValues(values);

    //pass sorted Array to get Missing Numbers
    List<Integer> results = getMissingNumbers(arrSorted);
    for (int value : results) {
        System.out.println(value);
    }
}

public static int[] sortValues(int[] arr) {
    // sort in asc first (any sort algo will do depending on the complexity you want
    // going with bubble sort
    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length; j++) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

public static List<Integer> getMissingNumbers(int[] arr) {
    List<Integer> missingNumbers = new LinkedList<>();
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] < arr[i + 1]) {
            if (arr[i + 1] - arr[i] != 1) {
                int rangeLeft = arr[i + 1] - arr[i];
                for(int k=1; k < rangeLeft; k++) {
                    missingNumbers.add(arr[i] + k);
                }
            }
        }
    }
    return missingNumbers;
  }
 }