Given an integer array of numbers 1 to n, you are 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 question can be easily solved, by calculating the sum of the n numbers, with the formula,
sum = (n * (n + 1)) / 2
A solution to this approach is given in this article.
But, this method cannot be used in the case, when the array contains more than one missing number.
For that condition, the BitSet utility class in Java can be used to solve the problem.
Approach:
- Find the number of missing elements from the given array, missCnt.
- Create a BitSet class object with n as a parameter.
- For each number in the given array, set its second last bit to true, using the BitSet.set() method.
- Initialize an integer variable lastMissIndex, to store the index of the last missing element.
- Using for loop from 0 to missCnt, find the first bit set false from lastMissIndex, using BitSet.nextClearBit() method.
- Increment lastMissIndex to 1, and print it.
Below is the implementation of the above approach
Java
// 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
This article is contributed by Nithiyashree M G.
