Example: FindMissingNumberSorting in Java

// FindMissingNumberSorting
import java.util.Arrays; // Required for Arrays.sort() and Arrays.toString()

public class Main {
    public static void main(String[] args) {
        int[] arr1 = {3, 1, 5, 2}; // Missing 4
        System.out.println("Array: " + Arrays.toString(arr1) + ", Missing number: " + findMissingNumberSorting(arr1));

        int[] arr2 = {1, 2, 3, 5, 6}; // Missing 4
        System.out.println("Array: " + Arrays.toString(arr2) + ", Missing number: " + findMissingNumberSorting(arr2));

        int[] arr3 = {2, 3, 4, 5}; // Missing 1
        System.out.println("Array: " + Arrays.toString(arr3) + ", Missing number: " + findMissingNumberSorting(arr3));

        int[] arr4 = {1, 2, 3, 4}; // Missing 5 (last element)
        System.out.println("Array: " + Arrays.toString(arr4) + ", Missing number: " + findMissingNumberSorting(arr4));
    }

    /**
     * Finds the missing number in an array by sorting and linear scanning.
     * Assumes numbers from 1 to n+1, with one number missing.
     *
     * @param arr The input array of distinct integers.
     * @return The missing integer.
     */
    public static int findMissingNumberSorting(int[] arr) {
        // Step 1: Sort the array. This makes the elements appear in ascending order.
        Arrays.sort(arr);

        // Step 2: Iterate through the sorted array and check for mismatches.
        // We expect arr[i] to be (i + 1) if no number is missing up to this point.
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != (i + 1)) {
                // If arr[i] is not (i + 1), then (i + 1) is the missing number.
                return (i + 1);
            }
        }

        // Step 3: If the loop completes, it means numbers 1 to arr.length are all present.
        // Therefore, the missing number must be (arr.length + 1).
        return arr.length + 1;
    }
}