Encontrar el número faltante de una array de enteros usando BitSet en Java

Dada una array de números enteros del 1 al n, se le pide que encuentre el número que falta en la array.

Ejemplo:

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.

Esta pregunta se puede resolver fácilmente, calculando la suma de los n números, con la fórmula,

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

Una solución a este enfoque se da en este artículo.

Sin embargo, este método no se puede utilizar en el caso de que la array contenga más de un número faltante.

Para esa condición, se puede usar la clase de utilidad BitSet en Java para resolver el problema.

Acercarse:

1. Encuentre la cantidad de elementos faltantes de la array dada, missCnt .
2. Cree un objeto de clase BitSet con n como parámetro.
3. Para cada número en la array dada, establezca su penúltimo bit en verdadero, usando el método BitSet.set() .
4. Inicialice una variable entera lastMissIndex, para almacenar el índice del último elemento faltante.
5. Usando for loop from 0 to missCnt , encuentre el primer bit establecido como falso desde lastMissIndex , usando el método BitSet.nextClearBit() .
6. Incremente lastMissIndex a 1 e imprímalo.

A continuación se muestra la implementación del enfoque anterior.

// 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);
    }
}

3
5
7
10

Este artículo es una contribución de Nithiyashree MG .