Find "Missing" Integer in a Java Array

Question

Given an array A[] of length n, find a "missing" number k such that:

• k is not in A
• 0<=k<=n

I've seen similar questions asked where the A[] contains numbers 1 to n with one number missing, but in this question, A[] can contain any numbers. I need a solution in O(n) time. For example,

A = {1,2,3} -> 0
A = {0,1,2} -> 3
A = {2,7,4,1,6,0,5,-3} -> 3,8

I've gotten as far as checking if 0 or n are in the array, and if not, return 0 or n, but I cannot seem to think of any other solution. This problem seems considerably more difficult given the fact that A can contain any numbers and not necessarily numbers 1 to n or something like that.

• Kane Templeton: Note: I know that only checking if 0 or n are not in the array will not give an accurate solution to most arrays.
• Jim Garrison: If A[] can contain any numbers, then what defines n. Is it the largest value in A? If so, what if the "missing" number is greater than the largest number? This question is underspecified.
• Maximilian Gerhardt: @JimGarrison array A[] of length n, so n = A.length, that's okay.
• Kane Templeton: Question is answered. Thank you all.

Answer 1

Linearly iterate over the array and "cross out" every number you encounter. Then iterate of that listed of crossed out numbers again and see which one is missing.

 public static int getMissingNumber(int[] A) 
 { 
 int n = A.length; 
 boolean[] numbersUsed = new boolean[n + 1]; //Because the definition says 0 <= k <= n, so k = n is also possible.
 for(int k = 0; k < n; k++) 
 {
 if(A[k] <= n && A[k] >= 0) //No negative numbers!
 numbersUsed[A[k]] = true;
 }
 for(int k = 0; k <= n; k++) 
 {
 if(numbersUsed[k] == false) 
 return k;
 } 
 return -1; //nothing found
 } 

Complexity is 2*n because of the two for loops, giving overall complexity O(n).

• Andreas: Third example indicates to return a list of all missing numbers, not just the first one.
• Maximilian Gerhardt: Indeed, OP can return a List<int> by iterating over all non-crossed out entries in the array. But the initial problem said to find a single number ("find a "missing" number k such that.."). I leave it to OP to edit the code :).
• Kane Templeton: Thank you very much. I feel dumb for not thinking of this.

Answer 2

Simple approach:

• initialize a set with all the values you need. (In your case number 0 to n)
• iterate over your arry and remove the number from the set
• at the end the set is giving you the missing entries.

• Kane Templeton: Good simple explanation. Thank you.

Answer 3

If you know that exactly one number is missing, there is a simple solution using xor.

static int missing(int[] arr) {
 int result = 0;
 for (int i = 0; i < arr.length; i++)
 result ^= (i + 1) ^ arr[i];
 return result;
}

If there may be more than one number missing you can return a Set like this:

static Set<Integer> missing(int[] arr) {
 Set<Integer> set = new HashSet<>();
 for (int i = 0; i <= arr.length; i++)
 set.add(i);
 for (int a : arr)
 set.remove(a);
 return set;
}

• Kane Templeton: Can you explain what result ^= (i + 1) ^ arr[i]; does?

Answer 4

Here is a solution that utilizes one loop. That's if we choose to ignore what Arrays.sort does

import java.util.Arrays;
class Solution {
 public int solution(int[] A) {
 Arrays.sort(A); 
 int min = 1; 
 for (int i = 0; i < A.length; i++){
 if(A[i]== min){
 min++;
 }
 } 
 min = ( min <= 0 ) ? 1:min;
 return min; 
 }
}

Answer 5

class Missing{
 public static void main(String[] args) {
 int arr[]={1,2,4,5,6,7,9};
 System.out.println(missingNumberArray(arr));
 }
 public static int missingNumberArray(int [] a) {
 int result=0;
 for(int i=0;i<a.length-1;i++){
 if(a[i+1]-a[i]!=1){
 result=a[i]+1;
 }
 }
 return result;
 }
 }
 //output:missing element is:3
 // missing element is:8

• Vivek: It is mainly used for finding only positive element .