I have an array 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 array, 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!
function findRepeat($numbers)
{
$numbersCount = count($numbers);
if ($numbersCount < 2) {
throw new InvalidArgumentException("Finding duplicate requires at least two numbers");
}
$n = $numbersCount - 1;
$sumWithoutDuplicate = ($n * $n + $n) / 2;
$actualSum = 0;
foreach ($numbers as $number) {
$actualSum += $number;
}
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 array.
additional space—the only additional space we use is for numbers to hold the sums with and without the repeated value.
If our array 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.
“Interview Cake takes the cake when it comes to interview prep. After studying for a little over 2 months, I finally cracked a technical interview and got an offer from my dream financial company! Thanks for all the help!
—
Fuad
Interview Cake
