Missing Element

Concept Description

Finding the missing element in a sorted array involves traversing the array and identifying the gap where the sequence breaks. Since the array is sorted, the missing element can be found more easily compared to an unsorted array. This task typically involves comparing adjacent elements or using binary search for optimization.

Java Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Main {
    public static int findMissingElement(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] + 1 != arr[i + 1]) {
                return arr[i] + 1;
            }
        }
        return -1; // No missing element
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5};
        System.out.println(findMissingElement(arr)); // Output should be 4
    }
}

C++ Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int findMissingElement(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] + 1 != arr[i + 1]) {
            return arr[i] + 1;
        }
    }
    return -1; // No missing element
}

int main() {
    int arr[] = {1, 2, 3, 5};
    cout << findMissingElement(arr, 4); // Output should be 4
    return 0;
}

Python Example

1
2
3
4
5
6
7
8
def find_missing_element(arr):
    for i in range(len(arr) - 1):
        if arr[i] + 1 != arr[i + 1]:
            return arr[i] + 1
    return -1  # No missing element

arr = [1, 2, 3, 5]
print(find_missing_element(arr))  # Output should be 4

In each example, the code defines a function that takes a sorted array as input. It then iterates through the array, checking the difference between adjacent elements. If the difference is not 1, it returns the missing element. If it goes through the entire array without finding a missing element, it returns -1.