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.

Note: I know that only checking if 0 or n are not in the array will not give an accurate solution to most arrays. — Kane Templeton
– Kane Templeton, Commented Mar 26, 2016 at 16:18
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. — Jim Garrison
– Jim Garrison, Commented Mar 26, 2016 at 16:43
@JimGarrison array A[] of length n, so n = A.length, that's okay. — Maximilian Gerhardt
– Maximilian Gerhardt, Commented Mar 26, 2016 at 16:44

Maximilian Gerhardt · Accepted Answer · 2016-03-26 16:38:36Z

5

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).

edited Mar 26, 2016 at 16:38

answered Mar 26, 2016 at 16:28

Maximilian Gerhardt

5,3633 gold badges34 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andreas Over a year ago

Third example indicates to return a list of all missing numbers, not just the first one.

Maximilian Gerhardt Over a year ago

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 Over a year ago

Thank you very much. I feel dumb for not thinking of this.

rpy · Accepted Answer · 2016-03-26 16:27:21Z

1

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.

answered Mar 26, 2016 at 16:27

rpy

4,0432 gold badges22 silver badges31 bronze badges

1 Comment

Kane Templeton Over a year ago

Good simple explanation. Thank you.

Paul Boddington · Accepted Answer · 2016-03-26 16:55:08Z

0

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

edited Mar 26, 2016 at 16:55

answered Mar 26, 2016 at 16:43

Paul Boddington

37.8k10 gold badges69 silver badges120 bronze badges

1 Comment

Kane Templeton Over a year ago

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

Timetrax · Accepted Answer · 2018-09-14 00:04:13Z

0

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

edited Sep 14, 2018 at 0:04

answered Sep 13, 2018 at 23:31

Timetrax

1,56315 silver badges17 bronze badges

Comments

subhashis · Accepted Answer · 2022-06-08 07:29:10Z

0

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

edited Jun 8, 2022 at 7:29

subhashis

4,9688 gold badges41 silver badges56 bronze badges

answered Sep 1, 2019 at 18:36

Vivek

11 silver badge4 bronze badges

1 Comment

Vivek Over a year ago

It is mainly used for finding only positive element .

Collectives™ on Stack Overflow

Find "Missing" Integer in a Java Array

5 Answers 5

3 Comments

1 Comment

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

1 Comment

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related