3 Easy Ways to Find the Missing Number in an Array in Java

Deepak Tewatia
1w
17
0
0

Article

Finding a missing number in an array is a common coding problem that helps improve your understanding of arrays, loops, and basic math. In this article, we’ll walk through three different methods to solve this problem step-by-step using simple language.

You are given an array that contains numbers from 1 to n, but one number is missing. Your task is to find that missing number. For example, if the array is {1, 2, 4, 5}, the missing number is 3.

Method 1. Using Sum Formula.

In this method, we use a simple math formula to find the missing number.

Steps

Find the total sum of numbers: The sum of the first n natural numbers is calculated using this formula: Sum=n×(n+1)2\text{Sum} = \frac{n \times (n+1)}{2}Sum=2n×(n+1)â€‹
Find the sum of the array: Add up all the numbers in the array.
Subtract the two sums: The difference between the total sum and the sum of the array gives the missing number.

Code Example

public class MissingNumber {
    public static int findMissingNumber(int[] arr, int n) {
        // Step 1: Calculate the total sum using the formula
        int totalSum = (n * (n + 1)) / 2;
        
        // Step 2: Calculate the sum of array elements
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        
        // Step 3: Subtract the actual sum from the total sum to get the missing number
        return totalSum - actualSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5}; // Missing number is 3
        int n = 5;
        System.out.println("Missing number: " + findMissingNumber(arr, n));
    }
}

How Does It Work?

The formula finds the sum of numbers from 1 to n.
We subtract the actual sum of the array from the total sum, which gives us the missing number.

Output

Method 2. Using XOR Operation.

This method uses a bitwise operation called XOR. XOR compares two numbers bit by bit. If two numbers are the same, XOR gives 0; if they are different, it gives 1. We can use this property to find the missing number.

Steps

XOR all the numbers in the array.
XOR all the numbers from 1 to n.
XOR the two results: The numbers that appear twice will cancel each other, leaving only the missing number.

Code Example

public class MissingNumberXOR {
    public static int findMissingNumberXOR(int[] arr, int n) {
        int xorArray = 0;
        int xorFull = 0;

        // Step 1: XOR all the elements in the array
        for (int num : arr) {
            xorArray ^= num;
        }

        // Step 2: XOR all the numbers from 1 to n
        for (int i = 1; i <= n; i++) {
            xorFull ^= i;
        }

        // Step 3: XOR the two results to get the missing number
        return xorArray ^ xorFull;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5}; // Missing number is 4
        int n = 5;
        System.out.println("Missing number: " + findMissingNumberXOR(arr, n));
    }
}

How Does It Work?

XORing the array numbers and numbers from 1 to n cancels out all the numbers except the missing one.

Output

Method 3. Sorting and Comparing.

In this method, we sort the array first and then compare each element with its expected value.

Steps

Sort the array.
Compare each element: After sorting, check if the number matches its position. If it doesn’t, that’s the missing number.

Code Example

import java.util.Arrays;

public class MissingNumberSorting {
    public static int findMissingNumberSorting(int[] arr, int n) {
        // Step 1: Sort the array
        Arrays.sort(arr);

        // Step 2: Compare the index with the element
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i + 1) {
                return i + 1;
            }
        }

        // Step 3: If no mismatch, return n as the missing number
        return n;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5}; // Missing number is 2
        int n = 5;
        System.out.println("Missing number: " + findMissingNumberSorting(arr, n));
    }
}