Find Missing Element

Array, Iterative approach

Given a sorted array of size n. Each element in the array is unique and lies from 1 to n+1. Find the missing element.

Solutions

This algorithm uses the formula for the sum of an arithmetic series to calculate the sum of all numbers from 1 to n+1, and then subtracts the sum of the elements in the array to find the missing element.

Approach - Iterative Technique

Iterates over the array and for each element, it calculates the sum of the first n+1 natural numbers (where n is the length of the array) using the formula (n + 1) * (n + 2) / 2.

Steps

1. Initialization: The function FindMissingElement is defined with one parameter, arr, which is the input array. It calculates the length of the array n and initializes a variable total to the sum of the first (n+1) natural numbers, which is calculated using the formula (n + 1) * (n + 2) / 2. This is based on the assumption that the array contains all numbers from 1 to n+1 with one missing number.

2. Subtraction: The function then iterates over each element in the array with i as the index. For each i, it subtracts arr[i] from total.

3. Return Result: After iterating over all elements, total will be equal to the missing number in the array, which is then returned by the function.

public class Solution
{
    public static int FindMissingElement(int[] arr)
    {
        int n = arr.Length;
        int total = (n + 1) * (n + 2) / 2;
        for (int i = 0; i < n; i++)
            total -= arr[i];
        return total;
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

public class Solution
{
    public int MissingNumber(int[] arr, int n)
    {
        int[] temp = new int[n + 1];

        for (int i = 0; i < n - 1; i++)
        {
            temp[arr[i] - 1] = 1;
        }

        int ans = 0;
        for (int i = 0; i <= n; i++)
        {
            if (temp[i] == 0)
                return i + 1;
        }
        return ans;
    }
}