Find out n numbers of missing elements from an array in java

This code uses a HashSet:

public static void main(String[] args) {
    int[] numbers = {9, 6, 4, 5, 7, 0, 1};
    Arrays.sort(numbers);
    HashSet<Integer> set = new HashSet<>();

    for (int i = numbers[0]; i < numbers[numbers.length - 1]; i++) {
        set.add(i);
    }

    for (int i = 0; i < numbers.length; i++) {
        set.remove(numbers[i]);
    }

    for (int x : set) {
        System.out.print(x + " ");
    }
}

will print:

2 3 8 

Here is how it works:
1. Adds all numbers from the minimum number of the array to the maximum number of the array to the set.
2. Iterates through the array and removes every item of the array from the set.
3. Prints the remaining items in the set, which are all the missing items of the array.

replace the else clause to be:

for(int j=numbers[i-1] + 1; j <= numbers[i] - 1; j++) {
    System.out.println( "Missing number is " + ( j ) );
}

let's examine the case: {9 ,6 ,4 ,5 ,7 ,0 , 1} after sorting it will be: {0, 1, 4, 5, 6, 7, 9} now if i is at index 2 it finds the difference between numbers[i] and numbers[i-1] to be not equal 1 (4 - 1 = 3), now you need ALL the numbers between 1 and 4 which are 2, 3 and thus you must loop from numbers[i-1] to numbers[i] (exclusive) in order to achieve this.

The complexity of this code is big O of N (O(N)), where N is the biggest element in your array.

There are a lot of questions which are unanswered here. For Example, Does an array always start with zero?, What is the maximum possible size? etc.

Here is a simple way to approach this problem,

• Find the maximum number in your set.
• Create an empty boolean array of the length as that of the max number you found in the last step plus one.
• Scan your original set and set the value of your new boolean array at the index equal to the number in your original set as true.
• Finally scan your boolean array to find and pront all the indices with value false.

Example:

Original Set: {1,0,3}

• Step 1: Maximum number in the set = 3
• Step 2: Boolean Array with Length = 3+1 --> {false, false, false, false}
• Step 3: While scanning original set and setting values in the boolean array this will be the final state --> {true, true, false, true}
• Step 4: You'll finally scan the boolean array to print 2 since this it is only index which has value = false

public class MissingElement {
    public static void main(String[] args)
    {
        int[] arr={10,9,8,7,5,4,3,1,2};
        Arrays.sort(arr);
        for(int i=0;i<arr.length-1;i++)
        {
            if(arr[i]+1!=arr[i+1])
            {
                System.out.println(arr[i]+1);
                break;
            }
        }
    }
}

int[] numbers = { 11, 6, 4, 5, 7, 1 };
Arrays.sort(numbers);
int numbersArrayIndex = 0;
for (int i = 0; i < numbers[numbers.length - 1]; i++) {
    if (i == numbers[numbersArrayIndex]) {
        numbersArrayIndex++;
    }
    else {
        System.out.println(i);
    }
}

        int[] a= {0,12,14,15,32};
        Arrays.sort(a);
        for(int i=0;i<a.length-1;i++)
        {
            if(a[i+1]-a[i]>1)
            {
                int temp=a[i+1]-a[i];
                for(int j=1;j<temp;j++) 
                {
                 System.out.print(a[i]+j + " ");
                }
                temp=0;
            }
        }

Output: 1 2 3 4 5 6 7 8 9 10 11 13 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

/*// This will work fine for Normal and duplicate elements
1. Find Largest no and create an array of size Largest+1 
2. Add all numbers from the 1 to till largest in set
3. Iterates through the array and remove every item of the array from the set.
4. Prints the remaining items in the set, which are all the missing items of the array.*/

        int numbers[] = { 3, 1, 5, 5 };

        int Largest = numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > Largest) {
                Largest = numbers[i];
            }
        }
        System.out.println("Largest no in given array -->" + Largest);
        
        HashSet<Integer> set = new HashSet<Integer>();

        int arr[] = new int[Largest+1];
        
         for (int i = 1; i < arr.length; i++) {
         set.add(i);
         }

        for (int j = 0; j < numbers.length; j++) {
            set.remove(numbers[j]);
        }

        System.out.println("Missing  no are :");
        for (int x : set) {
            System.out.print(x + " ");
        }   
    }
}

public static void printMissingNumbers(int[] arr) {
    int length = arr.length;
    int lastIndesx = arr[length - 1];

    while (length != 0) {
        if (arr[length - 1] == lastIndesx) {
            lastIndesx--;
            length--;
        } else {
            System.out.println("missing number :" + lastIndesx);
            lastIndesx--;
        }

    }

}

        public static void main(String[] args)
        {
        int[] arr = {1, 2, 3, 5};
        System.out.print("Given number is : ");
        for (int a : arr)
        {
            System.out.print(a + " ");
        }
        int lengthOfArray = arr.length + 1;
        int sum = lengthOfArray * (lengthOfArray + 1) / 2;
        int sumOfArrayNumber = 0;

        for (int s : arr)
        {
            sumOfArrayNumber = sumOfArrayNumber + s;
        }
        System.out.println();
        System.out.println("missing number is : " + Integer.valueOf(sum 
        - sumOfArrayNumber));
        }

I dont know if this will help you or not, but the same can be done using awk.

echo "13 2 5 9 4" | xargs | tr " " "\n" | sort -n | awk 'BEGIN { i=1}; {if (i!=$NF) {for(j=i;j<=$NF;j++) {if(j!=$NF) print j; i++}} else i++}'

1 3 6 7 8 10 11 12

Here largest no. in the array is consider as limit of sequence and awk will match each no. with a sequence of integer and if it does not match than it simply print the no.s