Daily bit(e) of C++ | Find the singular number
Daily bit(e) of C++ #219, Common interview problem: Find the singular number.
Today we will look at a common C++ interview: Find the singular number.
Given a sorted array of integers as std::vector<int>, where all values are present twice except for one singular number, return the singular number.
Your solution must run in O(logn) and use O(1) memory.
For example, for the input {1,1,4,4,5,5,7,9,9}, the result is 7.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/q6GbnEK1Y.
Solution
First, let’s consider what it means to have a sorted array where all values except for one are doubled up.
We will have a leading (potentially empty) sequence of values that occupy indexes 2*n and 2*n+1, after which we will have our singular number that will also occupy an even index (2*n), offsetting all following pairs of numbers by one.
We can therefore reformulate our goal. We are looking for the value of n, which maps to the position of the singular number, or more specifically, the minimum n for which value[2*n] != value[2*n+1].
This gives us a straightforward binary search over n, starting with the left boundary set to zero and the right boundary set to size()/2.
Or, more appropriately, without reimplementing existing algorithms.
