Bitset Strategy to Find Missing Elements

Concept Description

The Bitset strategy is a highly efficient approach to find missing elements in an array. It works particularly well when the array contains a series of integers with no duplicates and a known range. The primary idea is to create a bitset that has bits set for every element present in the array. Then, we iterate through the bitset to find which bits are not set, revealing the missing elements. The advantage of using a bitset is that it provides a compact storage solution and performs operations in constant time.

Java Example

 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
import java.util.BitSet;

public class Main {
    public static void findMissingNumbers(int[] arr, int count) {
        BitSet bitSet = new BitSet(count);
        
        for(int num : arr) {
            bitSet.set(num - 1);
        }
        
        int missingCount = count - bitSet.cardinality();
        
        int lastMissingIndex = 0;
        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 6, 7, 9, 10};
        int count = 10;
        findMissingNumbers(arr, count);
    }
}

C++ Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <bitset>
using namespace std;

void findMissingNumbers(int arr[], int n, int count) {
    bitset<100> bitSet;
    for(int i = 0; i < n; ++i) {
        bitSet.set(arr[i] - 1);
    }
    for(int i = 0; i < count; ++i) {
        if(!bitSet.test(i)) {
            cout << i + 1 << " ";
        }
    }
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 3, 5, 6, 7, 9, 10};
    int count = 10;
    findMissingNumbers(arr, 8, count);
    return 0;
}

Python Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def find_missing_numbers(arr, count):
    bitset = [0] * count
    
    for num in arr:
        bitset[num - 1] = 1
    
    for i, is_present in enumerate(bitset):
        if not is_present:
            print(i + 1)

arr = [1, 2, 3, 5, 6, 7, 9, 10]
count = 10
find_missing_numbers(arr, count)

In these examples, a bitset is used to represent the presence or absence of numbers. We then iterate through the bitset to find which numbers (bits) are not set, indicating the missing elements.