A fine day I came across an algorithmic challenge during an interview.

Suppose you have a list of contiguous numbers, but it is somehow missing out on one number in the list. For an example, take this:

4,5,6,7,8,9,10,11,12,14,15

The task was to find the missing number which in this case is 13.

I started with :

  • parse through the list
  • take the starting number
  • take the last number
  • take the sum of all the numbers in the list (sumA) = 101 calculate a sum using Arithmetic Progression summation formula n*(n+1)/2 (sumB) = 114
  • subtract the sum sumA from sumB
  • you get the missing number 🥳

While there seems nothing wrong with this, the solution would need me to parse through the whole list and then find the missing number.

This means an O(n) solution
So what comes to mind which is better than O(n) solution, an O(n-1) solution!!
J.K. — an O(log n) solution 😁

You should also notice that the list is sorted.
And which is the simplest and most basic use case of an O(log n) solution? — A binary search.
But, but, but, ..in a binary search we search for a given number within a list which is sorted.
Here the case is a little different.
Here you don’t know yet what you are looking for, in-fact that number is the thing you are supposed to find.
The interviewer provided me a very strong hint.
She says — “Look at the indices of the array items.”

Look at the list for a while, and then think, what numeric relation each number has with the index of it.

I’d suggest go one level deeper, think Normalisation.
Subtract the difference with the starting item, 4

So now the problem is reduced to → “in a given contiguous string of 0’s and 1’s, find the first 1’s position from the left”.
You can write your own binary search algorithm for finding the first 1 from this sorted list of 0s and 1s :
set left pointer at 0 & set right pointer as length-1
if list(right) equals 0, it means there is no 1 in the list, -1 is the answer
if list(left) equals 1, left is the solution
if list(right) equals 1 left and list(right-1) is 0, right is the solution
calculate mid as (left + right)/2
if list(mid) is 0, go step 1. with left = mid
if list(mid) is 1, go step 1. with right = mid
I’m calling this algorithm ‘Left-most-1’ algorithm for reference
I will do a dry run of the algorithm in a tabular form:
I will do a dry run of the algorithm in a tabular form:

So on the 5th step when it encounters the right pointer pointing to 1 and on the right-1 position as 0, it breaks with right pointer as the solution.
The complexity is O(log n)
So what does it all mean?
Basically it means that if I know that the left most 1’s position is on index 9, it means that on the main list, where list(9) is 14, the item missing would be list(9)-1 or 13.
All in O(log n)
It is imperative to understand that this algorithm needs a normaliser function to check for the number, so, in the above algorithm, just have a method which will basically find us the 4th row from Table 3 above.
The normaliser function for a given list, provided an index, would return you the
list(index)- list(0) — index
Here’s the modified ‘Left-most-1’ algorithm
Set left pointer at 0 & set right pointer as length-1
if normalised(right) equals 0, it means there is no 1 in the list, -1 is the answer :red_star:
if normalised(left) equals 1, left is the solution :green_star:
if normalised(right) equals 1 left and normalised(right-1) is 0, right is the solution :blue_star:
calculate mid as (left + right)/2
if normalised(mid) is 0, go repeat with left = mid
if normalised(mid) is 1, go repeat with right = mid
Here’s a working example of the same.

But why did I call this an ‘algorithm to rule them all’?
Okay, it is a bit of an overstatement, but I’ll tell you where all can this algorithm be applied:
Whenever you have a list which has ‘one type’ of elements on the left side and the rest of the elements on the right side. And you have to find that ‘boundary’.
So basically you just change the normaliser function we discussed above with whatever criteria you have to judge the elements as ‘one type’ than the other.
Just like in our given example we have a list the normaliser function determines if the item in the list is beyond the missing number or not, and just furnishes a 0 if it not beyond and furnishes 1 if it is beyond the missing number.
Now just apply this theory to different scenarios:
For example,
elements which are smaller than a certain number on the left, and elements which are greater than a certain number on the right, find the first item which is greater
all evens on the left and all odds on the right, find the first odd item
all strings starting with a vowel on the left and all strings starting with a consonant on the right, find the first string that starts with a consonant
Apply the ‘Left-most-1’ algorithm with the normaliser function based on the scenario and you get the solution in O(log n).