# Find missing number from list

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

"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 guys 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.remove(67);

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


//Output = 67

-
as sky said you can count list size(). If you want know the missing number, use a TreeSet instead of List , then parse it with Jeremy K finder –  cl-r Nov 12 '12 at 10:44

This is a very common question.Your algorithm is not correct.

The Rule is, find the sum of the numbers in the array and then subtract it from the the sum of numbers from 1 - 100. That is the missing the number you get.

Sum of natural number from 1 to N is NX(N+1)/2

-

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

1. Seperate 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 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.

-

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.

-