Efficient Java Program to Find Missing Number in Array

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 in an array of non-duplicating numbers from 1 to n, you can use the mathematical formula for the sum of the first n natural numbers. The sum of the first n natural numbers is given by the formula:

[ \text{Sum} = \frac{n \times (n + 1)}{2} ]

You can calculate the expected sum using this formula and then subtract the sum of the elements in the array from it. The difference will give you the missing number.

Here's an efficient Java program to implement this approach:

public class MissingNumberFinder {
    public static int findMissingNumber(int[] nums) {
        int n = nums.length + 1; // Since one number is missing
        int expectedSum = n * (n + 1) / 2; // Sum of first n natural numbers
        int actualSum = 0;

        // Calculate the sum of the elements in the array
        for (int num : nums) {
            actualSum += num;
        }

        // The missing number is the difference between expected and actual sum
        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 5, 6}; // Example array with missing number 3
        int missingNumber = findMissingNumber(nums);
        System.out.println("The missing number is: " + missingNumber);
    }
}

Explanation:

1. Input: The program takes an array of integers nums which contains numbers from 1 to n with one number missing.
2. Calculate Expected Sum: It calculates the expected sum of numbers from 1 to n using the formula.
3. Calculate Actual Sum: It iterates through the array to calculate the actual sum of the numbers present in the array.
4. Find Missing Number: The missing number is found by subtracting the actual sum from the expected sum.
5. Output: Finally, it prints the missing number.

Complexity:

• Time Complexity: O(n), where n is the number of elements in the array.
• Space Complexity: O(1), as we are using a constant amount of extra space.