Find all the missing number(s) 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 &lt; 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?
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 &gt; 0);
    assert(isSorted(elements));
    assert(elements[0] == 0);
    assert(first &lt;= last); 


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