Interview Cake

You're out of free questions.

Upgrade now

I have a list 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 list, 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!

def find_repeat(numbers_list): if len(numbers_list) < 2: raise ValueError('Finding duplicate requires at least two numbers') n = len(numbers_list) - 1 sum_without_duplicate = (n * n + n) / 2 actual_sum = sum(numbers_list) return actual_sum - sum_without_duplicate

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 list.

additional space—the only additional space we use is for numbers to hold the sums with and without the repeated value.

If our list 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?

Reset editor

Powered by qualified.io

. . .