Finding missing number(s) from an array

Question

Written this code, would like to get better approach using any algorithm to find missing numbers from an sorted or unsorted array. If its an unsorted array, i would sort and execute the following.

private static void identifyMissingValues(Integer[] ar) {
 for(int i = 0; i < (ar.length - 1); i++) {
 int next = ar[i + 1];
 int current = ar[i];
 if((next - current) > 1) {
 System.out.println("Missing Value : " + (current + 1));
 }
 }
 }

Any code faster or better than this, please suggest.

• Alex: if there's only one number missing from the sequence, you can sum up all the nubers you have, sum the whole expected sequence and then subtract one sum from another to get the missing number
• Rustam: if there two or more missed in a row only first will be printed

Answer 1

Any code faster or better than this, please suggest.

No there is no such thing - you cannot improve on an O(n) algorithm if every element must be visited.

• srikanth: Can we rewrite the code in any other fashion other than O(n) algorithm to find multiple missing values?
• OldCurmudgeon: @srikanth - Yes - but it will be less efficient.

Answer 2

Use BitSet instead of sorting.

 int[] ar = {7, 2, 6, 8, 10, 4, 3, 2};
 int min = IntStream.of(ar).min().getAsInt();
 BitSet b = new BitSet();
 for (int i : ar)
 b.set(i - min);
 int i = 0;
 while ((i = b.nextClearBit(i + 1)) < b.length())
 System.out.println(i + min);

result

5
9

Answer 3

Sorting the array would take O(n*log(n)).

You can do better if you add all the elements of the array to a HashSet (O(n)) running time, and then check for each number between 0 and ar.length - 1 (or whatever the relevant range is) whether the HashSet contains that number. This would take O(n) time.

• MrD: But why would you want to sort it?
• Eran: @MrD I wouldn't want to sort it - there OP does (If its an unsorted array, i would sort and execute the following.). That's why I offered an alternative that doesn't require sorting.
• srikanth: @Eran Using HashSet I.e time complexity (O(n)) is always better performed for larger data set. right?

Answer 4

Your approach is good, but I added something more for more than one numbers are missing..

eg : ar={1,2,4,6,10} // Sorted Array
private static void identifyMissingValues(Integer[] ar) {
 for (int i = 0; i < (ar.length - 1); i++) {
 int next = ar[i + 1];
 int current = ar[i];
 if ((next - current) > 1) {
 for (int ind = 1; ind < next - current; ind++)
 System.out.println("Missing Value : " + (current + ind));
 }
 }
}

Output is,

Missing Value : 3
Missing Value : 5
Missing Value : 7
Missing Value : 8
Missing Value : 9

• user4910279: Output must be 3 5 7 8 9.

Answer 5

Can I know the Input and Expected output number series ?
According to your code i feel the series should be a difference of 1,If i'm not wrong.

• Edgar Rokjān: It's not the answer. It should be posted like a comment.

Answer 6

So you have an array of n elements which starts with an integer i and contains all integers from i to i+n is that right? Eg:

arr = [1,2,3,4,5]

So, the sum of all numbers in the array should be the sum of numbers from i to i+n.

Eg: sum(arr) = 1+2+3+4+5 = 15

The formula for the sum of numbers 1 to n is n(n+1)/2

So you can have a for loop as:

int counter = 0;
for(Integer i : integers)
 counter += i

To get the sum of numbers in your array.

If your array starts at one, you check whether the counter variable equals n(n+1)/2, where n is the length of your array.

If your array doesn't start at one, for example arr = [78, 79, 80, 81] then you need to tweak this approach a little, but I'm sure you can figure it.

• Eran: How does that algorithm tell you which numbers are missing? (unless there's only one number missing, which doesn't seem to be the case based on the code in the question).

Answer 7

You can do:

Set<Integer> mySet = new TreeSet<Integer>(Arrays.asList(ar));
int min = mySet.first();
for (int i = 0; i < mySet.size(); i++) {
 int number = min + i;
 if (!mySet.contains(number)) {
 System.out.println ("Missing: " + number);
 i--;
 }
}

Answer 8

Integer [] list = new Integer[]{1, 12, 85, 6, 10};
Integer previous = null;
Arrays.sort(list);
System.out.println(list);
for(int index = 0; index < list.length; index++){
 if(previous == null){
 previous = (Integer) list[index];
 continue;
 }
 Integer next = previous + 1;
 if(((Integer) list[index] - previous) > 1){
 System.out.println("Missing value " + next);
 index--;
 }
 previous = next;
}