Search for the missing number in different ways

Every day developers solve different tasks. We usually have a lot of routine tasks and only a couple of them can be interesting and challenging. We may also be asked to solve a challenging task during the interview. Sometimes it’s important not only to be able to solve a problem, but also to think how effective our solutions are and how to optimize the complexity of our algorithms.

In this article we’re going to demonstrate that even a seemingly simple task can be optimized if you approach it creatively trying to solve it in different ways.

A list of numbers contains integers from 1 to N located randomly. The numbers appear on the list only once, and one of them is missing. Find the missing number.

1. So, we have a sourceList, and we know which integers it should contain. We can check if all numbers from 1 to sourceList.size are in the list:

We have for and operation in for List. It means that the complexity of the algorithm is n * n, which isn’t very good for such a simple task! How can we optimize the search process?

2. What happens if our sourceList will be sorted? Let’s see it.

We have the complexity: n * log (n) (sorting in middle way) + n. But our code depends on the sorting algorithm that will be chosen. We also have to create a new sorted list. This can be easily boosted by using a binary search, which is familiar to all the beginners as it’s studied in a base algorithm course. The complexity will be n * log (n) (sorting in middle way) + log (n).

3. I must confess, that was not the best choice as we have used a complicated sorting algorithm. We can use a linear algorithm for the list, if we have numbers from 1 to n in an unsorted list. We can create a new array and set source numbers in index positions equal to them, or we can mark the position as complete. In the end we will see a null (or false) in the missing position, it will be our result.

Now it looks better, n (initialization) + n (update) + n (search), but we had to create a new array.

4. Instead of an array or a list we can use a more suitable collection — HashSet. HashSet’s contains method has constant time complexity.

It is hash complexity * n and a new HashSet.

5. The drawback of the previous method is the necessity to create a new set, how can we find our element without it?

In fact, we have a cycle from 1 to n, which reminds a list of numbers from 1 to n. We have the full list and the sourceList in which one integer is still missing. If we subtract the sourceList from the full list, we’ll get the missed number. Perfect! The fifth solution is ready. But first we should remember our school years and resurrect the arithmetical progression sum formula.

S = (1 + n) * n / 2

Let’s implement it and don’t forget about the overflowing integer type.

Great! We have made the solution without a new data structure

Summary

Of cause, these aren’t all the possible solutions to the task. We can come up with new solutions or speed up the algorithms.

Thus, the article isn’t about finding a solution to the concrete task. The article demonstrates that while resolving the given task there can exist several options. Normally the process is a way from the most obvious solution to the most optimal and effective one. We cannot predict how many solutions the task may have, or when we should stop our optimizing process.

There is no limit to perfection!