Find missing number from list

Question

I was asked a question in an interview the other day:

You have an array list of numbers from 1 to 100, the problem is that one number is missing. How would you find that number?

This is a mock of the question. The code seems to work.

Could you give me some feedback?

private int count;

public void find() {
    //prep for question
    List<Integer> ints = new ArrayList();
    for (int i = 0; i < 100; i++) {
        ints.add(i);
    }
    ints.remove(67);

    //find the missing number
    for (Integer i : ints) {
        if (i != count) {
            System.out.println(count);
            count++;
        }
        count++;
    }
}

Output = 67

Answer 1

This is a very common interview question. However, your algorithm won't suffice: the array may be unsorted.

The method is to find the sum of the numbers in the array and then subtract it from the sum of numbers from 1 through 100. What's left over is what is missing from a complete list 1..100.

Sum of natural numbers \$1..N\ = \dfrac{N(N+1)}{2}\$.

Answer 2

I'm no Java guru but some things to consider might be:

1. Separate the UI display from the find algorithm i.e. don't have System.out.println in the method.

2. Supply the array list as a parameter to a method. So I would probably think the top level method to do this match might be something like

   public Integer getMissingValue(ArrayList<Integer> source) {
       // code
   }
   

   This way you could re-use the code in different contexts and even write some unit tests for it with varying values.

3. You code assumes the array list is sequential 1 - 100 does it not? I don't see that stated in the question. If the supplied list was in a random order I don't think your answer would work.

4. Make sure you read the question properly. It states integers 1 - 100. You have accounted for integers 0 - 99.

5. In an interview question like this I would always consider writing it using TDD. Interviewers like to see unit tests even if they don't ask for it. It shows you care about testing your code and also potentially shows good thought processes into the way you might take a problem.

Answer 3

If the list is ordered like in your example you could do something like:

for (int i = 0; i < ints.size(); ++i) {
    if (i + 1 != ints.get(i)) {
        return i + 1;
    }
}

The value will always be 1 more than the index (since you start at 1 and not 0) except for the missing number and the numbers that occur after it (which will be 2 ahead of the index). So you just return the first occurrence where it fails.

If the list is out of order, you could sort it first and then do the above.

Another option, which doesn't matter if the list is sorted or not, is to use sets. Explained here. Although this is probably overkill for only 1 missing element.

Answer 4

Well this is a well known 'brain teaser', and your solution is incorrect. You assume (and test by that assumption), that the input is ordered. Since this isn't mentioned in the question, the algorithm is incorrect - fix it first.

Answer 5

Your code has taken the long route to reach the destination.

For a better route, follow the below steps to find the missing number:

1. Find result1 \$= n * \dfrac{(n + 1)}{2}\$ (sum of natural numbers).

2. Then, iterate over the list and calculate sum of each element's value, then assign it to result2.

3. Finally, missing number will be result1 - result2.