I have a vector of n +
1 numbers. Every number in the range 1..n
appears once except for one number that appears twice.
Write a function for finding the number that appears twice.
We can do this with additional memory.
To avoid using up extra memory space, lets use some math!
First, we sum all numbers 1..n. We can do this using the equation:
\frac{n^2 + n}{2}
because the numbers in 1..n are a triangular series.
Second, we sum all numbers in our input vector, which should be the same as our other sum but with our repeat number added in twice. So the difference between these two sums is the repeated number!
unsigned int findRepeat(const vector<unsigned int>& numbers)
{
if (numbers.size() < 2) {
throw std::invalid_argument("Finding duplicate requires at least two numbers");
}
unsigned int n = static_cast<unsigned int>(numbers.size() - 1);
unsigned int sumWithoutDuplicate = (n * n + n) / 2;
unsigned int actualSum = accumulate(numbers.begin(), numbers.end(), 0U);
return actualSum - sumWithoutDuplicate;
}
time. We can sum all the numbers 1..n in time using the fancy formula, but it still takes time to sum all the numbers in our input vector.
additional space—the only additional space we use is for numbers to hold the sums with and without the repeated value.
If our vector contains huge numbers or is really long, our sum might be so big it causes an integer overflow. What are some ways to protect against this?
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
“It's a great source on thinking process training, one-of-a-kind, and not only for the interviews but for the day-to-day stuff also. Recommended if you don't know Knuth by heart!
—
Pavel
Interview Cake
