CODEWITHSUNDEEP
javaarraysnumbers
Kane Templeton
Kane Templeton

Reputation: 61

Find "Missing" Integer in a Java Array

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

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.

Upvotes: 1

Views: 3341

Answers (5)

Vivek
Vivek

Reputation: 1

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

Upvotes: 0

Timetrax
Timetrax

Reputation: 1493

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

Upvotes: 0

Paul Boddington
Paul Boddington

Reputation: 37645

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

Upvotes: 0

Maximilian Gerhardt
Maximilian Gerhardt

Reputation: 5353

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

Upvotes: 5

rpy
rpy

Reputation: 4013

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.

Upvotes: 1

Related Questions