How to find a missing number with a range of millions of numbers in an array where duplicates are present?

Question

Im asking this question in relation to this question posted a few months ago

Currently, in the app I am working, I get series of numbers where numbers may be missing and duplicated but are ordered in ascending manner.

There were two problems.

1. If there were not duplicates, finding the missing number was pretty easy using the method suggested in the accepted answer of the mention question.

2. But, if there are duplicates, that approach doesnt work anymore.

How can I solve the problem? No logic seems to work out. And even if it would(using loop), it wouldn't be efficient.

NOTE: I also searched for some libraries but couldn't find any.

Answer 1

I just tried to see if breaking down the tasks as much as I can using Fork Join as a fun exercise to get to know the library better (also because I thought dividing the task down into smaller tasks and processing it parallelly would take less time) and contrasted it with a simple for loop.

public class misc {
    public void getMissingNumbers(int[] numbers){
        for (int i=0; i<numbers.length -1; i++){
            int current = numbers[i];
            int next = numbers[i+1];
            if(current+1 != next){
                System.out.println("Problem! - "+current+" "+next);
            }
        }
    }
     
     public static void main(String []args){
         int[] range = IntStream.rangeClosed(1, 50_000_000).toArray();
         int index = 50000;
         range[index] =  range[index-1];  //duplicate
         index = 390;
         range[index] =  range[index-1];
         index = 500390;
         range[index] =  range[index-1];
         index = 2500390;
         range[index] =  range[index-1];
         
         ZonedDateTime now = ZonedDateTime.now();
         misc m = new misc();
         m.getMissingNumbers(range);
         System.out.printf("%s exec time: %dms\n",
                 m.getClass().getSimpleName(),
                 ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
         
         now = ZonedDateTime.now();
         ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
         breakDownRecursively bdr = new breakDownRecursively(range);
         forkJoinPool.invoke(bdr);
         System.out.printf("%s exec time: %dms\n",
                 bdr.getClass().getSimpleName(),
                 ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));
     }
}

class breakDownRecursively extends RecursiveAction {
    private final int[] arr;
    private final ArrayList<Integer> arrlst = new ArrayList<>();
    
    public breakDownRecursively(int[] arr) {
        this.arr = arr;
    }
    
    public void compute() {
        int n = arr.length;
        if (arr.length < 2) return;
        int mid = arr.length / 2;

        int[] left = new int[mid];
        System.arraycopy(arr, 0, left, 0, mid);

        int[] right = new int[arr.length - mid];
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        invokeAll(new breakDownRecursively(left), new breakDownRecursively(right));
        compare(left, right);
    }
    
    private void compare(int[] left, int[] right) {
        if (left.length == 1 && right.length == 1) {
            if (left[0]+1 != right[0]) {
                //System.out.println("Problem! - "+left[0]+" "+right[0]);
            }
        }
    }
}

Output:

Problem! - 390 390
Problem! - 390 392
Problem! - 50000 50000
Problem! - 50000 50002
Problem! - 500390 500390
Problem! - 500390 500392
Problem! - 2500390 2500390
Problem! - 2500390 2500392
misc exec time: 60ms
Problem! - 390 392
Problem! - 500390 500392
Problem! - 2500390 2500392
breakDownRecursively exec time: 2435ms

I suppose I probably made a mistake somewhere during implementation of the fork join, but at the very least you should see that a for loop isn't THAT bad.

and when I used Runnable:

     int mid = range.length/2;
     int[] half1 = new int[mid+1];
     System.arraycopy(range, 0, half1, 0, mid+1);
     int[] half2 = new int[mid];
     System.arraycopy(range, mid, half2, 0, range.length - mid);
     RunnableTask r1 = new RunnableTask(half1);
     RunnableTask r2 = new RunnableTask(half2);
     now = ZonedDateTime.now();
     Thread t1 = new Thread(r1);
     Thread t2 = new Thread(r2);
     
     t1.start();
     t2.start();
     t1.join();
     t2.join();
     
     System.out.printf("%s exec time: %dms\n",
             r1.getClass().getSimpleName(),
             ChronoUnit.MILLIS.between(now, ZonedDateTime.now()));

class RunnableTask implements Runnable{
    private final int[] arr;
    public RunnableTask(int[] arr) {
        this.arr = arr;
    }
    @Override
    public void run() {
        // TODO Auto-generated method stub
        for (int i=0; i<arr.length -1; i++){
            int current = arr[i];
            int next = arr[i+1];
            if(current+1 != next){
                System.out.println("Problem! - "+current+" "+next);
            }
        }
    }
    
}

Output:

Problem! - 390 390
Problem! - 390 392
Problem! - 50000 50000
Problem! - 50000 50002
Problem! - 500390 500390
Problem! - 500390 500392
Problem! - 2500390 2500390
Problem! - 2500390 2500392
RunnableTask exec time: 49ms

Only slightly better than a for loop.

Answer 2

A binary search benefits from being able to cut a problem space in half, and then eliminating one of the halves. In this case, any half that contains both a missing value and a duplicate is indistinguishable from one that doesn't, no matter how many additional duplicates exist, so you'd end up having to process both halves.

Millions of integer comparisons requires very little compute time. A linear solution would still be very fast, and in this case, is as efficient as you can be on a worst-case basis.

I ran the code multiple times below on my desktop, and came up with an average of about 5ms to process an array of 10 million elements, and in all cases, it found the results in under 10ms.

public class Millions {

    public static int[] fillArray(int size) {
        int[] ar=new int[size];
        int randomPos=(int)(Math.random()*size);
        System.out.println("Placing missing value at position " + randomPos);
        int nextNum=1;
        for (int i=0; i<size; i++) {
            if (i==randomPos) {
                nextNum+=2;
            } else {
                if (Math.random() > 0.999995) {
                    System.out.println("Placing duplicate value at position " + i);
                } else {
                    nextNum++;
                }
            }
            ar[i] = nextNum;
        }
        return ar;
    }

    public static int missingValue(int[] ar) {
        for (int i=1; i<ar.length; i++) {
            if (ar[i]-ar[i-1]==2) return ar[i]-1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int SIZE=10000000;
        int[] ar=fillArray(SIZE);
        long start=System.currentTimeMillis();
        int missing=missingValue(ar);
        long duration=System.currentTimeMillis()-start;
        if (missing<0) {
            System.out.println("No missing value found.");
        } else {
            System.out.println("Missing value = " + missing);
        }
        System.out.println("Duration : " + duration + " ms");
    }
}

Answer 3

As far as I know, there is no way to detect a missing number in a list except for looping through.

If your array is sorted, it should look like something like this:

[1,2,3,3,4,6]

So, this code should do the work:

int getMissingNumber(int[] numbers){
    for (int i=0; i<numbers.length -1; i++){
        int current = numbers[i];
        int next = numbers[i+1];
        if(next - current > 1){
            return current + 1;
        }
    }
    return -1;
}

Other than this, there is the option of changing the Array to the Set and then back to Array and then, use the previous approach. Be sure to use LinkedHashSet to preserve insertion order. But I don't know if it would be any faster.