Find all the missing number(s)

Question

Recently I've attended an interview, where I faced the below question:

Question: "There is an sorted array. You need to find all the missing numbers. Write the complete code, without using any generics or inbuilt function or binary operators. First and last terms will be given. Array will be sorted. Array always starts with zero."

Example:

Input:
int array[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };

Output:
Missing number(s): 5, 16, 17, 19, 22.

If its single missing term, we can calculate the required total using summation formula, and find the difference between the actual total. Which gives the missing term.

Since there are multiple values missing, I came up with below approach.

Code:

public class MissingNumber {

    public static int count = 0;
    public static int position = 0;
    public static boolean flag = false;

    public static void main(String[] args) {

        int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };

        findMissingNumbers(a, position);

    }

    private static void findMissingNumbers(int a[], int position) {

        if (position == a.length - 1)
            return;

        for (; position < a[a.length - 1]; position++) {

            if ((a[position] - count) != position) {
                System.out.println("Missing Number: " + (position + count));
                flag = true;
                count++;
                break;
            }
        }

        if (flag) {
            flag = false;
            findMissingNumbers(a, position);
        }
    }

}

Output:

Missing Number: 5
Missing Number: 16
Missing Number: 17
Missing Number: 19
Missing Number: 22

This gives the required solution. But, is the code fine or can this be done with a better approach?

Answer 1

There are three places where numbers may be missing:

• before the first number in the array ;
• inside the array ;
• after the last element in the array.

Here is what I would do:

static void findMissingNumbers(int[] a, int first, int last) {
            // before the array: numbers between first and a[0]-1
    for (int i = first; i < a[0]; i++) {
        System.out.println(i);
    }
            // inside the array: at index i, a number is missing if it is between a[i-1]+1 and a[i]-1
    for (int i = 1; i < a.length; i++) {
        for (int j = 1+a[i-1]; j < a[i]; j++) {
            System.out.println(j);
        }
    }
            // after the array: numbers between a[a.length-1] and last
    for (int i = 1+a[a.length-1]; i <= last; i++) {
        System.out.println(i);
    }
}

Example of usage:

public static void main(String[] args) {
    int a[] = { 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a, 0, 25);
}

Answer 2

The problem as stated was:

There is an sorted array. You need to find all the missing numbers. Write the complete code, without using any generics or inbuilt function or binary operators. First and last terms will be given. Array will be sorted. Array always starts with zero.

When I ask questions like this in interviews, one of the things that I'm looking for is can the candidate read a specification and make good decisions on implementing it? The spec says what the inputs are and what the outputs are, so I would expect that somewhere in the code there would be a method with signature

int[] findMissingElements(int[] elements, int first, int last)

Note that the method is not void. This idea that a method prints out its result is found only in interviews and college assignments; it is nowhere found in industry.

I would also like to see some verification of the method preconditions given. If the method is private then an assertion is appropriate. I'd also like to see the candidate take initiative to add some more preconditions that I did not give. I often give underspecified problems to see how the candidate deals with ambiguity: by asking clarifying questions, or by ignoring the problem and hoping for the best. In this case it is not stated that first is less than or equal to last but it seems reasonable to assume that.

int[] findMissingElements(int[] elements, int first, int last)
{
    assert(elements.Count > 0);
    assert(isSorted(elements));
    assert(elements[0] == 0);
    assert(first <= last); 

If the method is public then these should be if(!precondition) throw ...

Answer 3

Regarding your current code:

Public or private

You have three public static variables, but your findMissingNumbers method is private. It would be better having it the other way around. You wouldn't want outside code to modify your static variables, those are meant to be used only by your findMissingNumbers method.

The findMissingNumbers method that you provide is meant to be a method that provides some calculations, it should be able to be called from other classes - hence it should be public.

Naming

boolean flag = false; It's a boolean, of course it's a flag! What is the flag used for? Reading this variable name now doesn't help me understand the variable's purpose at all. It should describe why it is being used.

Static variables

public static int count = 0;
public static int position = 0;
public static boolean flag = false;

Having static variables are usually only used for constants. Are these variables supposed to be constants? Constants should be marked final. If you would mark them final you will quickly see that you will get compiler errors on count and on flag, because you modify those values inside the method. There is a good reason to not use them as public static variables!!

Consider what would happen if your main method would look like this:

public static void main(String[] args) {
    int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a, position);

    int b[] = { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 23 };
    findMissingNumbers(b, position);
}

After the first call to findMissingNumbers, your public static variables would have changed, which would modify the behavior of the second method call. Actually, in this case it would change the behavior in such a big way that it would cause a StackOverflowError. These two method calls should be independent.

By the way: I think that the position parameter that you send to the method is not needed, the method should start searching at zero by default.

Solution:

Use more local variables. boolean flag does not need to be a static variable. It should only be used within the method itself. It should be a local variable and initialized to false. Making this change actually solves the StackOverflowError that would occur when calling this method twice.

The variables that is used inside the method, and gets changed, can be passed as parameters to the method. position is already a parameter so the public static variable is in fact not used, other than to provide a starting value to the method.

To provide default values for the method, we can use a method that only calls the "real" method with some parameters.

Here is a better implementation with these flaws fixed of your code. Note that one of the findMissingNumbers methods are public (as it is the one that is meant to be called), while one remains private. Also note the improved variable names, and how the parameters are passed between the methods - removing the big flaw of static variables.

public static void main(String[] args) {

    int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a);
    
    int b[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(b);

}

private static void findMissingNumbers(int values[], int position, int count) {
    boolean foundMissingNumber = false;
    if (position == values.length - 1)
        return;

    for (; position < values[values.length - 1]; position++) {

        if ((values[position] - count) != position) {
            System.out.println("Missing Number: " + (position + count));
            foundMissingNumber = true;
            count++;
            break;
        }
    }

    if (foundMissingNumber) {
        findMissingNumbers(values, position, count);
    }
}

public static void findMissingNumbers(int values[]) {
    findMissingNumbers(values, 0, 0);
}

Another improvement that would be helpful to make is to let your methods return the missing numbers, instead of doing the output inside the method. Consider for example if you would want to calculate the sum of the missing numbers, or the sum of the squares of the missing numbers. Currently, you would perhaps do some code duplication (which is a known code smell) to do this, but if you let your methods return the missing numbers, you would not need to do any code duplication. I'd recommend looking into a ArrayList<Integer> for returning the values.

Answer 4

Just a few thoughts on how you might improve your algorithm as stated:

1. The question doesn't state that there will always be a missing number. So might it be good (given that the first value is guaranteed to be 0 so array[0] == 0) then if array[n] != n you have 'missing' values.
2. If we accept that we have missing values in that case, then the difference between n and the value stored in array[n] tells us how many 'missings' we have.

Those two bits of information would allow us to truncate your algorithm to:

1. Do no work if there are no missing values.
2. Stop work as soon as it finds the requisite number of 'missings'.

Answer 5

In addition to comments about static (global variables...), naming variables correctly (Boolean flag) and other tidbits that others have mentioned, I think two things haven't been mentioned: Code doesn't meet spec, and it's missing summation formula option.

Your code doesn't meet the specs as listed.

The spec asks for output:

Missing number(s): 5, 16, 17, 19, 22.

Your code however shows:

Missing Number: 5 
Missing Number: 16 
Missing Number: 17 
Missing Number: 19 
Missing Number: 22

That's not the right output.

You should pair @EricLippers suggest of a method that uses

int[] findMissingElements(int[] elements, int first, int last)

with a secondary method to print out the resulting array

void printElement(int[] elements)

---

public static void main(String[] args) {
    int a[] = { 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    int b[] = findMissingNumbers(a, 0, 25);
    printArrayToScreen(b[]);
}
int[] findMissingElements(int[] elements, int first, int last) {
    ...
}
void printArrayToScreen(int[] elements){
    ...
}

It separates the responsibilities. It will make future changes easier

• What happens when you need to change the algorithm but don't want to affect the printing?
• Add another method for unsorted arrays?
• Add tests for the algorithm? For the printing?
• Print to screen?
• Format for Website in HTML
• Send to another process/application

Its missing summation formula option

If its single missing term, we can calculate the required total using summation formula, and find the difference between the actual total. Which gives the missing term.

IF the array is missing one item, use summation formula to determine missing item:

a[] = {0,1,3}
4 = `1,3` = 1 + 3
6 = 1 + 2 + 3
2 = 6 - 4
2 is *the* missing number

That could be easier than going through an unknown number of elements. programmers like options after all :)

public static void main(String[] args) {
    int start = 0;
    int end = 5;
    int a[] = {0, 1, 3, 4, 5};
    b[]  = findMissingNumbers(a, start, end);
    printArrayToScreen(b[]);
}
int[] findMissingNumbers(int[] elements, int first, int last) {
    // Length is End+1 with 0 added. Are we only missing one item?
    int numMissing = a.Length - (last + 1);
    if (numMissing = 1) return findMissingNumber(a, start, end);
    // Otherwise, find missing numbers
    ....
}
int[] findMissingNumber(int[] elements, int first, int last) {
    ...
}
void printArrayToScreen(int[] elements){
    ...
}

You want to separate the methods so you can change A without affecting B and A can reused elsewhere.

Answer 6

The other answers about style and encapsulation are correct, but they miss an important optimization. Given a number of missing values m, and a total array length n, your solution and the others on this page return in O(n) time. You can actually do this in just O(m log n) time.

The main insight here is that given the length of the sorted input array, you can tell how many numbers are missing for any given set of endpoints. If the number of indexes matches the number of expected values (i.e. 10 numbers expected in an array of length 10), you can safely assume that no numbers are missing.

Therefore, if you bisect the array recursively, like in binary search, then it should be easy to tell if either half contains no missing numbers, and only investigate the halves that don't.

0 1 2 4 5 7 8 9 10 11 12 13 14 15  // missing 3 and 6
[-----------] [-----------------]
7 indices,    7 indices,
9 values:     7 values
2 missing     0 missing: do not evaluate!

0 1 2 4 5 7 8
[-----] [---]
4 idxs  3 idxs
5 vals  4 vals
1 msng  1 msng

It follows that your recursive function should look roughly like this:

int[] missingValues(int[] inputArray, int startIndex, int endIndex, int min, int max)

...which is left as an exercise to the reader. :) Naturally, if there are a lot of missing numbers, this algorithm might not beat an O(n) algorithm, but if m is much less than log2(n) this is by far a better algorithm.

Answer 7

From a once over, possibly repeating some of the other answers:

• static -> I don't see a good reason
• You are mixing computation and output, for interviews, that's a strike against you
• main gets called with an array of arguments, for extra points in an interview I would have checked for arguments and use those
• You have zero comments, and some tricky parts, strike 2
• flag.. -> that is too generic a name
• position -> seems like a useless static actually, you could just do findMissingNumbers(a, 0);
• From an OO perspective you would want to re-use that code, that'll be hard if your one interesting method is private ;)
• The questions states : First and last terms will be given. You are not using any first or last term in your code, strike 3

I like to think I can read Java pretty okay. But I can't figure out what your code does. You have a problem when it is easier to run your code through a debugger to see what it does than simply reading it.

Answer 8

You can use logic to compare current and previous number. If the current value is greater than the previous by more than 1, then add 1 to the current value for length = difference value.

int prev = a[0];
int current = 0;

for(int i=1;i<a.length;i++)
{
 current = a[i];
 int differenceValue = current-prev;
 if(differenceValue  > 1)
  {
     for(int j=1;j<differenceValue;j++)
     System.out.println("Missing Value : "+(prev+j));
  }
}