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:
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