How to find the missing number in an integer array of 1 to 100 in Java?

To find the missing number in an integer array containing numbers from 1 to 100, you can use a mathematical approach involving the sum of natural numbers.

Understanding the Method

The key idea is that the sum of the first N natural numbers (1, 2, 3, ..., N) can be calculated using the formula N * (N + 1) / 2. In our scenario, N is 100. We can calculate the expected sum of numbers from 1 to 100. Then, we will calculate the sum of numbers present in the input array. The missing number can be found by subtracting the sum of the input array from the expected sum.

Step-by-Step Solution in Java

Here's how to implement this in Java:

Calculate the expected sum: Use the formula N (N + 1) / 2* where N=100.
- Expected Sum = 100 * (100 + 1) / 2 = 5050
Calculate the actual sum of the array elements: Iterate over the array and add up all the elements.
Find the missing number: Subtract the calculated sum of the array elements from the expected sum (5050). The result will be the missing number.

Java Implementation

public class MissingNumber {

    public static int findMissingNumber(int[] arr) {
        int n = 100;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }


    public static void main(String[] args) {
          int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
                41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
                61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
                81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99}; //Missing 100
          int missing = findMissingNumber(array);
        System.out.println("Missing number is " + missing); // Output: Missing number is 100
      }
}

Example

If the input array is {1, 2, 3, ..., 99}, then the missing number will be 100. Because the expected sum (1+2+...+100) is 5050. Sum of array elements is 4950 (1+2+...+99). The missing number will be 5050 - 4950 = 100.

Advantages

Efficiency: This method is efficient as it avoids the use of multiple loops, it is has an O(n) time complexity for the summation of the array elements and is overall much faster then sorting or using bit manipulation.
Simplicity: The code is easy to understand and implement.

Reference Information

According to the reference, the formula for the sum of natural numbers from 1 to N is N*(N+1)/2. To find the missing number, the sum of the array elements should be subtracted from this sum when N is equal to 100.

askvity