If the number is an integer from 1 to n, you will be asked to find the missing number from the array.

Example:

Input : n = 5, a[] = {1, 2, 4, 5}
Output: 3
Explanation: From the array of numbers 1 to 5, 3 is missing.

Input : n = 10, a[] = {1, 3, 4, 6, 8, 10}
Output: 2, 5, 7, 9
Explanation: From the array of numbers 1 to 10, 2, 5, 7 and 9 are missing.

This problem can be easily solved by calculating the sum of n numbers according to the formula:

sum = (n * (n + 1)) / 2

A solution to the present approach is given during this article.

But, this method can't be utilized in the case, when the array contains quite one missing number.

For that condition, the BitSet utility class in Java can be used to solve the problem.

Approach:

1. Find the amount of missing elements from the given array, missCnt.
2. Create a BitSet class object with n as a parameter.
3. For each number within the given array, set its second last bit to true, using the BitSet.set() method.
4. Initialize an integer variable lastMissIndex, to store the index of the last missing element.
5. Using for loop from 0 to missCnt, find the primary bit set false from lastMissIndex, using BitSet.nextClearBit() method.
6. Increment lastMissIndex to 1, and print it.

Below is the implementation of the above approach

// Java Program to find the missing elements
// from integer array using BitSet class

import java.io.*;
import java.util.*;

public class FindMissingNo {
	private static void findMissingNumbers(int arr[], int n)
	{
		int missCnt = n - arr.length;
		// create Bitset object b
		BitSet b = new BitSet(n);
		for (int i : arr) {
			b.set(i - 1);
		}
		int lastMissIndex = 0;
		for (int i = 0; i < missCnt; ++i) {
			lastMissIndex = b.nextClearBit(lastMissIndex);
			// print missing number
			System.out.println(++lastMissIndex);
		}
	}
	public static void main(String[] args)
	{
		int n = 10;
		// array of 10 numbers
		int[] arr = new int[] { 1, 2, 4, 6, 8, 9 };
		// call function
		findMissingNumbers(arr, n);
	}
}

Output

3
5
7
10