Given an array of non-duplicating numbers from 1 to n where one number is missing, write an efficient java program to find that missing number.

To find the missing number efficiently, we can use the sum formula for the first n natural numbers, which is given by:

int sum(int n) {
    return n * (n + 1) / 2;
}

This formula computes the expected sum of numbers from 1 to n. We can then subtract the actual sum of the elements in the array from this expected sum to find the missing number. Here’s how we can implement this:

public class MissingNumber {
    public static int findMissingNumber(int[] nums) {
        int n = nums.length + 1; // Since one number is missing
        int expectedSum = sum(n);
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

The time complexity is O(n) due to the single loop through the array, and the space complexity is O(1) since we use only a few extra variables. This approach is optimal and straightforward.

Another efficient method to find the missing number is to use the XOR operation. The key idea is that XORing a number with itself results in 0, and XORing a number with 0 results in the number itself. By XORing all numbers from 1 to n with the numbers in the array, we can isolate the missing number. Here’s how this can be implemented:

public class MissingNumber {
    public static int findMissingNumber(int[] nums) {
        int n = nums.length + 1;
        int xorFull = 0;
        int xorArray = 0;

        for (int i = 1; i <= n; i++) {
            xorFull ^= i;
        }
        for (int num : nums) {
            xorArray ^= num;
        }
        return xorFull ^ xorArray;
    }
}

This method runs in O(n) time and requires O(1) space. The XOR trick is particularly elegant and often surprises interviewers, showcasing a deeper understanding of bit manipulation.

A more straightforward approach is to sort the array and then find the missing number by scanning through it. While this method is less efficient than the previous two, it’s a good way to demonstrate understanding of sorting algorithms. Here’s how it can be implemented:

import java.util.Arrays;

public class MissingNumber {
    public static int findMissingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // The missing number
            }
        }
        return nums.length + 1; // If missing number is n
    }
}

In this approach, we first sort the array, which takes O(n log n) time, then we check for the missing number in a single pass, giving a total complexity of O(n log n). The space complexity is O(1) if we sort in place. While this isn't the most efficient method, it’s still a valid approach and can be useful in scenarios where sorting is already part of the problem.