Interview Problem: Finding a Deleted Element in O(N)

Everyone is used to thinking that technical interviews involve very complex tasks that only a mid-level specialist or higher can solve.

Spoiler alert: it’s not true. Sometimes all it takes to solve a problem is a basic knowledge of the language and a little imagination.

Let’s look at one of these problems and explore its solution using Python as an example. We’re confident you’ll be able to easily transfer this solution to any other language. 

Problem statement

So, here’s the problem.

You are given an ordered sequence of numbers from 1 to N. One of the numbers is removed. The remaining numbers are shuffled randomly. Find the removed number.

Incidentally, this same problem often appears under the guise of “Find a duplicate in a numerical sequence.” The reasoning is the same 

A head-on solution

It would seem that the solution to the problem is obvious. We can sort the shuffled sequence again. After that, we compare the original sequence and the resulting one up to the first discrepancy. As soon as we encounter a discrepancy, there it is, the answer! The secret was easy to open.

However, it’s not that simple. Sure, you solved the problem, but in a highly suboptimal way. Consider the complexity of sorting a shuffled sequence O(NlogN), such as quicksort or mergesort. Furthermore, we’re also searching for discrepancies in sorted arrays. Searching a sorted array has complexity O(N), meaning that in the worst case, if the largest element is removed, we’ll have to iterate through the entire array.

Total complexity of the algorithm: O(NlogN) + O(N) = O(NlogN).

Not bad, but could be better. At least a plus O(N)!

The right decision

An observant candidate would have noticed that only one number was removed. This means that the sums of all the elements in the original and shuffled lists differ by exactly the removed number!

So why do we need the information that the list was sorted first and then shuffled? It’s simple—to confuse the candidate and test their attentiveness.  So, here’s a simple algorithm to implement:

1. Find the sum of the initial sequence
2. Find the sum of the shuffled sequence
3. Subtract the second from the first – that’s the result.

In Python, the solution takes two lines (function findDel):

Essentially, we do three operations.

• The first is the summation of the initial sequence. It goes without gaps, so we’re dealing with an arithmetic progression. The sum of an arithmetic progression is calculated using the formula (a_1+a_n)*n/2. The complexity of this operation is O(1), since the sequence is ordered, and increasing the number of elements doesn’t complicate our calculations.

Note: If the initial sequence were unordered, we would have to find the maximum and minimum to use the formula above. This immediately entails additional sorting. In this case, it’s probably better to sum all the elements element-by-element, as the complexity of this operation will no longer be O(1).

• The second operation is summing the shuffled sequence. This is no longer an arithmetic progression, since an element is missing. The sequence is also unsorted, so we simply add all the terms element by element to calculate the sum. In Python, the sum function does this for us. The complexity of this operation is O(N), since iterates over all the elements.
• The last operation is to subtract the result of one from the other. Subtracting two numbers has complexity O(1).

So, the final complexity of the algorithm is O(1) + O(N) + O(1) = O(N). Not O(1), of course, but better than O(NlogN)the first solution.

Conclusion

We’ve solved a very simple problem, but even here there’s room for improvement—you can search for a more optimal solution and practice calculating the complexity of algorithms.

Explore More IT Terms